L 418. Sentence Screen Fitting ---M

 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:

1. A word cannot be split into two lines.
2. The order of words in the sentence must remain unchanged.
3. Two consecutive words in a line must be separated by a single space.
4. Total words in the sentence won't exceed 100.
5. Length of each word is greater than 0 and won't exceed 10.
6. 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.

A:

首先想到的就是一行一行去Fill 着看。

哎，比较笨。  更新就是，line 26, 如果line 很长， 则直接increase res, and by moving startCol

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62

class Solution { public: int wordsTyping(vector<string>& sentence, int rows, int cols) { int n = sentence.size(); vector<int> V(n,0); for(int i =0;i<n;i++){ V[i] = sentence[i].length() + ( i==0?0:V[i-1] ); } int res = 0; backtracking(V, rows, cols, 0,0,res, 0); return res; } private: void backtracking(vector<int>& V, const int rows, const int cols, int startRow, int startCol, int & res, int startV){ int n = V.size(); if(startRow >= rows){ return; } if(startCol >= cols){ backtracking(V,rows, cols,startRow+1, startCol-cols, res, startV); return; } // incase a big cols, int totalV = V.back() + V.size()-1; while(cols - startCol >= totalV+1){ if(startCol == 0){ startCol += totalV; }else{ startCol += totalV+1; // 1 for space before first word } res++; } int remain = cols - startCol; int endV = n-1; int preStartVCount = startV ==0? 0 : V[startV-1]; while( endV >= startV){ int len = V[endV]-preStartVCount+endV-startV; if(startCol !=0){ len ++; // need an space before first word } if(remain>= len){ // backtracking again from endV int nextRow = startRow; if(endV == n-1){ res++; } backtracking(V,rows,cols,startRow, startCol+ len, res, ( (endV+1)% n) ); return; }else{ if(endV == startV){ endV--; }else{ endV = startV + (endV- startV)/2; } } } // cannot fit any word, we will start from a new row backtracking(V, rows, cols, startRow+1, 0, res, startV); } };

当然也可以把上面的backtracking 写成while loop.