Sentence Screen Fitting

https://leetcode.com/problems/sentence-screen-fitting/description/

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:

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 is greater than 0 and 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.

Thoughts

naive的方法是对每个单词判断它能否在该行装下, 不能则下一行, 知道所有行走完. 缺点是当单词很短而格子很大时TLE, 因为时间复杂度为O(rows * cols). https://discuss.leetcode.com/topic/62455/21ms-18-lines-java-solution/3?page=1 换个角度看, 可以看成把(带好空格的)sentence无限前后相连, 每一行就像是一个固定size为cols的窗口不断往前移动, 一共能移动rows次. 每次把窗口起点start从当前位置往后移动cols位置, 当落下的位置为" "意味着没有词被切开, start + 1移到下一个完整的词. 否则表明词被从中切开, 整个词不能放入该窗口(row), 需要把下一个窗口(row)的起点往前移动到该单词的起点.

更近一步还可以提前存下一个单词中每个字母离前面" "距离是多少.

Code

class Solution {
    public int wordsTyping(String[] sentence, int rows, int cols) {
        String s = String.join(" ", sentence) + " ";
        int len = s.length(), start = 0;
        int[] map = new int[len];
        for (int i = 1; i < len; i++) {
            map[i] = s.charAt(i) == ' ' ? 1 : map[i - 1] - 1;
        }
        for (int i = 0; i < rows; i++) {
            start += cols;
            start += map[start % len];
        }

        return start / s.length();
    }
}

Analysis

时间复杂度O(N + rows).