418. Sentence Screen Fitting

Description

Given arows x colsscreen and a sentence represented by a list ofnon-emptywords, findhow many timesthe 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.

Method 1

Iterate Rows, for each row, insert word into cols. If, cols is not long enough or 0, move to next row.

But LTE.

Code

class Solution2 {
public:
    int wordsTyping(vector<string>& sentence, int rows, int cols) {
        int Counter = 0;
        int wordIndex = 0;
        bool excesive = false;
        if(0 == sentence.size() || cols == 0 || rows == 0) {
            return Counter;
        }

        while(rows > 0) {
            int curCol = cols;
            while(curCol > 0) {
                if(sentence[wordIndex].size() > curCol) {
                    break;
                }
                // insert word
                curCol -= sentence[wordIndex].size();
                // append space
                if(curCol > 0) {
                    curCol -= 1;
                }

                ++wordIndex;

                if(wordIndex == sentence.size() ) {
                    ++Counter;
                    wordIndex = 0;
                }
            }
            --rows;
        }
        return Counter;
    }
};

Method 2

Think from another direction:

1. total length is rows * cols, length of sentence is sum of words + space
2. Ideally, times = rows * cols / sum of (words + space). But something was not counted.
   1. what if a col is not enough to load another word
   2. what if the col is only enough for a word without tailing space

Code

class Solution {
public:
    int wordsTyping(vector<string>& sentence, int rows, int cols) {
        //int Counter = 0;
        string combine;
        for(auto word : sentence) {
            combine+=word;
            combine.push_back(' ');
        }

        int curLen = 0;
        while(rows > 0) {
            curLen += cols;
            if(' ' == combine[(curLen - 1) % combine.size()]) {
                //curLen += 1;
            }
            else {
                // not enough for this word
                if(combine[(curLen - 1) % combine.size() + 1] != ' ') {
                    while(0 != curLen && combine[(curLen - 1) % combine.size()] != ' ') {
                        --curLen;
                    }
                    //cout << curLen << endl;
                }
                // end of a word without tailing space
                else {
                    curLen += 1;
                }
            }
            --rows;
        }

        //cout << curLen << endl;
        return curLen / combine.size();
    }
};