1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public int wordsTyping(String[] sentence, int rows, int cols) {
        int count = 0, currRow = 0, ptr = 0, size = 0;
        while (currRow < rows) {
            while (ptr < sentence.length && size + sentence[ptr].length() + 1 <= cols + 1) {
                size += sentence[ptr].length() + 1;
                ptr += 1;
            }
            if (ptr == sentence.length) {
                count += 1;
                ptr = 0;
            } else {
                size = 0;
                currRow += 1;
            }
        }
        return count;
    }
}

Brute force.
一行一行的填. size表示当前行填满的个数. count表示重复了几次. ptr指的是当前的sentence. 由于必须要空格间隔, 于是可以认为每个sentence自带一个空格, 于是每个sentence的length要 + 1. 一个edge case就是如果一个sentence刚好fit到一行中的最后几个位置, 此时不需要空格. 那么我们可以认为只要size小于等于cols + 1即可. 因为如果等于cols + 1, 那必然是最后一个空格超出了, 这是没问题的.

时间复杂度: O(rows * cols / (sum(sentence.length())). 我们是一个个去看是否fit, 然后不断增加size.
空间复杂度: O(1)