Monday, October 5, 2020

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.  








at

No comments:

Post a Comment