Given a rows x cols screen and a sentence represented by a list of 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 won't exceed 10.1 ≤ rows, cols ≤ 20,000.Example 1:Input:rows = 2, cols = 8, sentence = ["hello", "world"]Output: 1Explanation:hello---world---The character '-' signifies an empty space on the screen.Example 2:Input:rows = 3, cols = 6, sentence = ["a", "bcd", "e"]Output: 2Explanation:a-bcd- e-a---bcd-e-The character '-' signifies an empty space on the screen.Example 3:Input:rows = 4, cols = 5, sentence = ["I", "had", "apple", "pie"]Output: 1Explanation:I-hadapplepie-Ihad--The character '-' signifies an empty space on the screen.

先来一个brute force, 类似Text Adjustment

1 public class Solution { 2     public int wordsTyping(String[] sentence, int rows, int cols) { 3         if (sentence==null || sentence.length==0 || sentence.length>rows*cols || rows<=0 || cols<=0) 4             return 0; 5         int res = 0; 6         int j = 0; //indicate the index of string in sentence that is currently trying to be inserted to current row 7         int row = 0; //current row 8         int col = 0; //current col 9         10         while (row < rows) {11             while (col + sentence[j].length() - 1 < cols) {12                 col = col + sentence[j].length() + 1;13                 j++;14                 if (j == sentence.length) {15                     res++;16                     j = 0;17                 }18             }19             row++;20             col = 0;21         }22         return res;23     }24 }

但是在稍微大一点的case就TLE了，比如：

["a","b","e"] 20000 20000， 花了465ms

所以想想怎么节约时间，

提示是可以DP的，想想怎么复用，refer to: https://discuss.leetcode.com/topic/62364/java-optimized-solution-17ms

如果这一行由sentence里面某一个string开头，那么，下一行由哪个string开头，这个是确定的；同时，本行会不会到达sentence末尾，如果会，到几次，这个也是一定的

这两点就可以加以利用，因为我们找到了DP的复用关系

sub-problem: if there's a new line which is starting with certain index in sentence, what is the starting index of next line (nextIndex[]). BTW, we compute how many times the pointer in current line passes over the last index (times[]).

Time complexity : O(n*(cols/lenAverage)) + O(rows), where n is the length of sentence array, lenAverage is the average length of the words in the input array.

1 public class Solution { 2     public int wordsTyping(String[] sentence, int rows, int cols) { 3         int[] nextInt = new int[sentence.length]; 4         int[] times = new int[sentence.length]; 5         for (int i=0; i