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: 
1

Explanation:
hello---
world---

The character ‘-‘ signifies an empty space on the screen.
Example 2:

Input:
rows = 3, cols = 6, sentence = ["a", "bcd", "e"]

Output: 
2

Explanation:
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: 
1

Explanation:
I-had
apple
pie-I
had--

The character ‘-‘ signifies an empty space on the screen.

 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 }

 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<sentence.length; i++) {
 6             int cur = i; //try to insert string with index cur in sentence to current row
 7             int col = 0; //current col
 8             int time = 0;
 9             while (col + sentence[cur].length() - 1 < cols) {
10                 col = col + sentence[cur++].length() + 1;
11                 if (cur == sentence.length) {
12                     cur = 0;
13                     time++;
14                 }
15             }
16             nextInt[i] = cur;
17             times[i] = time;
18         }
19         
20         int res = 0;
21         int cur = 0;
22         for (int i=0; i<rows; i++) {
23             res += times[cur];
24             cur = nextInt[cur];
25         }
26         return res;
27     }
28 }