Sentence Screen Fitting

Description

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.

Hint

Train of Thought

21ms:

Say sentence=["abc", "de", "f], rows=4, and cols=6.
The screen should look like

"abc de"
"f abc "
"de f  "
"abc de"
Consider the following repeating sentence string, with positions of the start character of each row on the screen.

"abc de f abc de f abc de f ..."
 ^      ^     ^    ^      ^
 0      7     13   18     25
Our goal is to find the start position of the row next to the last row on the screen, which is 25 here. Since actually it's the length of everything earlier, we can get the answer by dividing this number by the length of (non-repeated) sentence string. Note that the non-repeated sentence string has a space at the end; it is "abc de f " in this example.

Here is how we find that position. In each iteration, we need to adjust start based on spaces either added or removed.

"abc de f abc de f abc de f ..." // start=0
 012345                          // start=start+cols+adjustment=0+6+1=7 (1 space removed in screen string)
        012345                   // start=7+6+0=13
              012345             // start=13+6-1=18 (1 space added)
                   012345        // start=18+6+1=25 (1 space added)
                          012345

DP:
把sentence中的每个单词在行首出现的次数记为times[i], 如果当前行首为第i个单词, 下一行开头的单词记为next[i]
e.g
[a, bcd, e] row = 3. col = 6
a-bcd- 
e-a---
bcd-e-
next[0] = 2, times[0] = 0,
next[2] = 1, times[2] = 1,
next[1] = 0, times[1] = 1,

Code

//optimized solution
public class Solution {
    public int wordsTyping(String[] sentence, int rows, int cols) {
        String s = String.join(" ", sentence) + " ";
        int start = 0, l = s.length();
        for (int i = 0; i < rows; i++) {
            start += cols;
            if (s.charAt(start % l) == ' ') {
                start++;
            } else {
                while (start > 0 && s.charAt((start-1) % l) != ' ') {
                    start--;
                }
            }
        }

        return start / s.length();
    }
}


//DP:
public class Solution {
    /**
     * if exists a word's length > col, return 0 
     * all words must be put on the screen that can be count as 1 time
     * 
     */ 
    public int wordsTyping(String[] sentence, int rows, int cols) {
        int[] next = new int[sentence.length];//if current row begins with this word, what word occur in the beiginning of next line
        int[] dp = new int[sentence.length];//how many times the pointer in current line passes over the last index 

        for (int i = 0; i < sentence.length; i++) {
            int cur = i;//current word in the beginning
            int time = 0; 
            int curLen = 0;//current words' length in this row

            while (curLen + sentence[cur].length() <= cols ) {
                curLen += sentence[cur].length() + 1; // 当前单词可能直接顶到行末, 但是要判断还能不能放下新单词要加一个空格
                cur++;
                if (cur == sentence.length) {//如果已经把所有的单词都放了一遍了
                    cur = 0;
                    time++;
                }
            }

            //if current row cannot contain any more word
            next[i] = cur;
            dp[i] = time;
        }

        int res = 0;
        int cur = 0;
        for (int i = 0; i < rows; i++) {
            res += dp[cur];
            cur = next[cur];
        }

        return res;
    }
}

Complexity