## Sunday, October 9, 2016

### LeetCode 418 - 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:
apple
pie-I

The character '-' signifies an empty space on the screen.```

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

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

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

Brute Force
```    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;
}```