暴力模拟会超时。因此必须一行行直接放，不能一个个word放。

这种方法很巧妙，把word整合成一个string，单词间用空格分隔，最后也加一个空格。

用一个变量记录当前已经在screen上放了多少个字符，记为count。因此 count%n 下一个要放的字符。

对于每一行，先假设cols个字符都能放上去，count += cols。下一个字符 s[count%n] 应当放在下一行。

但是，很可能当前行是没法放满cols的字符的。

如果下一个字符 s[count%n] = ‘ ’，我们应当在当前行多放一个空白字符，即 ++count。

如果下一个字符 s[count%n] != ‘ ’，说明可能有word被切断了，这是不合法的。因此，我们得减少当前行的字符数量，直到 s[(count-1)%n] == ‘ ’。

最后的结果就是能放下的字符数count/n。

 

时间复杂度：O(rows * average word length)

空间复杂度：O(# of words * average word length)，因为把所有字符拼接到了一起。

 

/*count: how many characters of the reformatted sentence is on the screencount % length of reformatted sentence: the starting position of the next rowAnswer: count / length of reformatted sentence*/class Solution {public:    int wordsTyping(vector
     
      & sentence, int rows, int cols) {        string s="";        for (auto x:sentence)             s += x+' ';                int count=0;        int n=s.size();        for (int i=0;i
      
       0 && s[(count-1)%n]!=' ') --count;            }        }        return count/n;    }};
      
     

 

References: