LeetCode 418 - Sentence Screen Fitting

http://bookshadow.com/weblog/2016/10/09/leetcode-sentence-screen-fitting/

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:

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 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.

X.
https://github.com/YaokaiYang-assaultmaster/LeetCode/blob/master/LeetcodeAlgorithmQuestions/418.%20Sentence%20Screen%20Fitting.md

This is a Greedy approach. Since we want to know how many times the given sentence can be fitted, we are actually looking for the MAXIMUM time the given sentence can be fitted. Hance, we can try to put as many words in one line as possible, making up the greedy aporoach. In this process, we first try to put as many words in one line as possible and trim the tailing words that does not fit in that line as a whole, leaving all remaining positions in that line after trimming empty (as space). Then we continue filling next line by starting from the word after the last word in previous line. In this process we can make use of modulo operation to deal with the wrapping back issue for the sentence.

Since there should be at least space between two words, we first add one space between each word and join the sentence. Remember to add one space after the last word as well.

Then we consider each row sequentially. Using start to represent the number of characters we have put. For each row, we first try to put cols character from the joined sentence s into one line start from start (Maximum number of characters we can put into this line). Then we check the next position after the last position of this line. There are 2 conditions:

1. If the next position is a space, then this line can fit all words we put in, we add one to start according to the implicit space in this case.
2. If the next position is not space, we check for the current position. And we remove all characters that are not space until we meet one since this last word we just removed cannot be fit in this line. In this process, we subtract 1 from start during each character being removed.

At last, the start represents the length of the repeated lines in which each word is separated by exactly one space. And since the joined sentence s has its words separated by 1 space as well, the number of repeats we can get is start / s.length().

Given there are n characters in sentence[]

Time complexity: O(rows + n)

Space complexity: O(n)

https://blog.csdn.net/magicbean2/article/details/78319388
把所有的字符串都加起来，然后每次看如果位移一整行的距离是否正好落在这个字符串的空格位置，如果不是的话就退后，直到遇到一个空格。
http://www.cnblogs.com/grandyang/p/5975426.html

这道题给我们了一个句子，由若干个单词组成，然后给我们了一个空白屏幕区域，让我们填充单词，前提是单词和单词之间需要一个空格隔开，而且单词不能断开，如果当前行剩余位置放不下某个单词，则必须将该单词整个移动到下一行。我刚开始想的是便利句子，每个单词分别处理，但是这种做法很不高效，因为有可能屏幕的宽度特别大，而单词可能就一两个，那么我们这样遍历的话就太浪费时间了，应该直接用宽度除以句子加上空格的长度之和，可以快速的得到能装下的个数。这是对于只有一行的可以直接这么做，难点在于剩下的空格不足以放下一个单词，就得另起一行。比如例子2中的第二行，a后面有三个空格，无法同时放下空格和bcd，所以bcd只能另起一行了。所以并不是每个位子都是可用的，我们需要记录有效空位的个数。还是拿例子2来举例，句子的总长度的求法时要在每个单词后面加上一个空格(包括最后一个单词)，所以需要匹配的字符串是 a_bcd_e_，一共8个字符。每行有6个空位，我们用变量start来记录有效位的个数，先加上第一行的空位数，那么start即为6，我们先算start%len=6%8=6，然后all[6] = 'e'，不是空格，不会进入if循环。为啥要判断这个呢，由于题目中说了如果某个单词刚好填满一行时，之后就不用加空格了，下一个单词可以从下一行的首位置开始，就像例子3中的第二行一样。那么什么时候会进入if从句呢，当 all[start%len]==' ' 的时候，此时start应该自增1，因为虽然剩余的位置刚好填满了单词，后面不用再加空格了，但是我们再算有效空位个数的时候还是要加上这个空格的。然后我们开始处理第二行，start再加上这行的长度，此时start为12，算start%len=12%8=4，然后all[4] = 'd'，不是空格，不进入if从句。我们进入else从句，这里我们需要移除不合法的空位，此时我们需要算 (start-1)%len = 3，all[3] = 'c'，不为空，所以start自减1，为11。然后再算(start-1)%len = 2，all[2] = 'b'，不为空，所以start自减1，为10。然后再算(start-1)%len = 1，all[1] = ' '，为空，跳出循环。我们在第二行减去了2个不合法的空位，再来到第三行，start再加上这行的长度，此时start为16，算start%len=16%8=0，然后all[0] = 'a'，不是空格，不进入if从句。我们进入else从句，这里我们需要移除不合法的空位，此时我们需要算 (start-1)%len = 7，all[7] = ' '，为空，跳出循环。最后用start/len=16/8=2，即为最终答案

https://medium.com/@rebeccahezhang/leetcode-418-sentence-screen-fitting-9d6258ce116e
https://discuss.leetcode.com/topic/62455/21ms-18-lines-java-solution

1. String s = String.join(" ", sentence) + " " ;. This line gives us a formatted sentence to be put to our screen.
2. start is the counter for how many valid characters from s have been put to our screen.
3. if (s.charAt(start % l) == ' ') is the situation that we don't need an extra space for current row. The current row could be successfully fitted. So that we need to increase our counter by using start++.
4. The else is the situation, which the next word can't fit to current row. So that we need to remove extra characters from next word.
5. start / s.length() is (# of valid characters) / our formatted sentence.

    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();
    }

https://discuss.leetcode.com/topic/62364/java-optimized-solution-17ms

public int wordsTyping(String[] sentence, int rows, int cols) {
        int[] nextIndex = new int[sentence.length];
        int[] times = new int[sentence.length];
        for(int i=0;i<sentence.length;i++) {
            int curLen = 0;
            int cur = i;
            int time = 0;
            while(curLen + sentence[cur].length() <= cols) {
                curLen += sentence[cur++].length()+1;
                if(cur==sentence.length) {
                    cur = 0;
                    time ++;
                }
            }
            nextIndex[i] = cur;
            times[i] = time;
        }
        int ans = 0;
        int cur = 0;
        for(int i=0; i<rows; i++) {
            ans += times[cur];
            cur = nextIndex[cur];
        }
        return ans;
    }

https://discuss.leetcode.com/topic/62297/a-simple-simulation
http://bookshadow.com/weblog/2016/10/09/leetcode-sentence-screen-fitting/

上例中apple单词的相对位置从第二行开始循环，因此只需要找到单词相对位置的“循环节”，即可将问题简化。

利用字典dp记录循环节的起始位置，具体记录方式为：dp[(pc, pw)] = pr, ans

以数对(pc, pw)为键，其中pw为单词在句子中出现时的下标，pc为单词出现在屏幕上的列数

以数对(pr, ans)为值，其中pr为单词出现在屏幕上的行数，ans为此时已经出现过的完整句子数

def wordsTyping(self, sentence, rows, cols): """ :type sentence: List[str] :type rows: int :type cols: int :rtype: int """ wcount = len(sentence) wlens = map(len, sentence) slen = sum(wlens) + wcount dp = dict() pr = pc = pw = ans = 0 while pr < rows: if (pc, pw) in dp: pr0, ans0 = dp[(pc, pw)] loop = (rows - pr0) / (pr - pr0 + 1) ans = ans0 + loop * (ans - ans0) pr = pr0 + loop * (pr - pr0) else: dp[(pc, pw)] = pr, ans scount = (cols - pc) / slen ans += scount pc += scount * slen + wlens[pw] if pc <= cols: pw += 1 pc += 1 if pw == wcount: pw = 0 ans += 1 if pc >= cols: pc = 0 pr += 1 return ans

X. DP

同样也需要统计加空格的句子总长度，然后遍历每一行，初始化colsRemaining为cols，然后还需要一个变量idx，来记录当前单词的位置，如果colsRemaining大于0，就进行while循环，如果当前单词的长度小于等于colsRemaining，说明可以放下该单词，那么就减去该单词的长度就是剩余的空间，然后如果此时colsRemaining仍然大于0，则减去空格的长度1，然后idx自增1，如果idx此时超过单词个数的范围了，说明一整句可以放下，那么就有可能出现宽度远大于句子长度的情况，所以我们加上之前放好的一句之外，还要加上colsRemaining/len的个数，然后colsRemaining%len是剩余的位置，此时idx重置为0

    int wordsTyping(vector<string>& sentence, int rows, int cols) {
        string all = "";
        for (string word : sentence) all += (word + " ");
        int res = 0, idx = 0, n = sentence.size(), len = all.size();
        for (int i = 0; i < rows; ++i) {
            int colsRemaining = cols;
            while (colsRemaining > 0) {
                if (sentence[idx].size() <= colsRemaining) {
                    colsRemaining -= sentence[idx].size();
                    if (colsRemaining > 0) colsRemaining -= 1;
                    if (++idx >= n) {
                        res += (1 + colsRemaining / len);
                        colsRemaining %= len;
                        idx = 0;
                    }
                } else {
                    break;
                }
            }
        }
        return res;
    }

https://github.com/YaokaiYang-assaultmaster/LeetCode/blob/master/LeetcodeAlgorithmQuestions/418.%20Sentence%20Screen%20Fitting.md

For each row on the screen, it must start with a word in the sentence. Thus there exists some overlapping subproblems here, which is when the given row starts with a specific word, how many words it can contains. And for those subproblems, we have optimal solutions for them, constitute of the optimal substructures in DP. Hence for this question, we can utilize dynamic programming to solve it.

First, we construct dp[] array in which dp[index] means if a given row starts with word sentence[index], then the next row must starts with word sentence[dp[index]].

Then for each row with a start index k (for first row it should be 0) indicating the index of the first word in sentence, we count the number of words it contains based on the previous dp[] array. The next row should starts with dp[k]. We continue this process and count the number of words we can store in all rows.

Then the answer should be count / sentence.length.

Time complexity: O(sentence.length + rows).

Space complexity: O(sentence.length)

https://eugenejw.github.io/2017/08/leetcode-418

It is like a jump game, when the any of the word in sentence falls into a position that it has fallen into before,
we know that the string filling patten starts to repeat itself. Then we do not need to proceed.

Note that, a better solution is here, which I believe is the same idea but does not do the actual word pointer forwarding.

    public int wordsTyping(String[] sentence, int rows, int cols) {
        int count=0, j=0, rowsCountDown=rows;
        int[] dp = new int[rows+1];
        while (rowsCountDown > 0) {
            int i = 0;
            if (rowsCountDown!=rows && j==0)   break; // break if the first word repeats the pattern.
            while (i <= cols && i+sentence[j].length()<=cols) {
                i += sentence[j].length() + 1;
                j++;
                if (j == sentence.length) {
                    j = 0;
                    count++;
                }

            }
            
            rowsCountDown--;
            dp[rows-rowsCountDown] = count;
        }

        if (rowsCountDown == 0) {
            return count;
        }
        int remainder = (rows % (rows-rowsCountDown));
        return (rows / (rows-rowsCountDown))*count + dp[remainder];
    }

Brute Force
http://www.itdadao.com/articles/c15a559599p0.html

    public int wordsTyping(String[] sentence, int rows, int cols) 
    {
        int m = sentence.length;
        int res = 0;
        int c = 0;
        int left = cols;
        for(int i = 0; i < rows;)
        {
            if(sentence[c%m].length() <= left)
            {
                if(c%m == m-1) res++;
                c++;
                left = left - sentence[(c-1)%m].length() - 1;
                
            }
            else
            {
                i++;
                left = cols;
            }
        }
        return res;        
    }