Sentence Screen Fitting

题目
Given a rows x cols screen and a sentence represented by a list of non-empty words, find how many times the given sentence can be fitted on the screen.

Note:

A word cannot be split into two lines.
The order of words in the sentence must remain unchanged.
Two consecutive words in a line must be separated by a single space.
Total words in the sentence won't exceed 100.
Length of each word is greater than 0 and won't exceed 10.
1 ≤ rows, cols ≤ 20,000.

答案
有一个huge case过不了

class Solution {
    public int wordsTyping(String[] sentence, int rows, int cols) {
        int num_sentences = 0;
        int curr_word_idx = 0;

        int curr_col = 0;
        for(int i = 0; i < rows; i++) {

            // speed up
            if(i > 0 && curr_col == 0 && curr_word_idx == 0) {
                // Now we know sentence can be fitted num_sentences times in k = i rows.
                int k = i;
                int remain_rows = rows - k;
                int t = (remain_rows / k);
                if(t != 0) {
                    // Update num sentences and i
                    num_sentences += t * num_sentences;
                    i = i + k * t - 1;
                    continue;
                }
            }

            // Can this word fit into this row ?
            int remain_cols = cols - curr_col;
            // No
            if(remain_cols < sentence[curr_word_idx].length()) {
                curr_col = 0;
                continue;
            }
            // Yes
            curr_col = curr_col + sentence[curr_word_idx].length() + 1;

            if(curr_word_idx == sentence.length - 1) num_sentences++;
            curr_word_idx = (curr_word_idx + 1) % sentence.length;

            // If after adding this word, curr_col >= cols, then start next row(also reset curr_col = 0), otherwise stay in the same row
            if(curr_col < cols) i--;
            else curr_col = 0;
        }
        return num_sentences;
    }
}

class Solution {
    public int wordsTyping(String[] sentence, int rows, int cols) {

        String reformatted = String.join(" ", sentence) + " ";

        int cnt = 0, n = reformatted.length();
        for(int i = 0; i < rows; i++) {
            cnt += cols;
            if(reformatted.charAt(cnt % n) == ' ') {
                // If we see a space, that means cnt is right after some word, add 1 to cnt to point to next word
                cnt++;
            }
            else {
                // If we see a char, cnt is pointing at the middle of some word, so current row does not have enough space for this word
                while(cnt > 0 && reformatted.charAt((cnt - 1) % n) != ' ') cnt--;
            }

        }
        return cnt / n;
    }
}