# 0418. Sentence Screen Fitting
###### tags: `Leetcode` `Medium` `Dynamic Programming`
Link: https://leetcode.com/problems/sentence-screen-fitting/
## 思路
思路[参考](https://leetcode.com/problems/sentence-screen-fitting/solutions/90845/21ms-18-lines-java-solution/)
直觉的思路是我们先给string里面的所有sentence中间加上空格得到新字符串```s``` 然后我们看```rows*cols```里面能塞进去几个加完空格的字符串
但是问题在于有一些空格是不需要的(如果一个单词刚好在一行的结尾结束，那么我们不需要加上它后面的空格)还有一些空格是要额外加上去的(如果这一行不够放最后一个单词)
如果在```rows*cols```的基础上再加上/减去上面说的这些空格再除以```s```的长度就是答案
我们用dp计算如果某一行以```s[i]```结尾我们要加/减的空格个数```map[i]```
We want to find the start position of the row next to the last row on the screen, which should be 25 in the example below.
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

用下一行的起始位置除以加了空格的sentence长度 就是一共能塞下几个加了空格的字符串
那么我们该如何计算每行的起始位置呢
对于下一行来说 我们首先用这一行的起始位置+```cols```得到如果不考虑空格和要保留字串完整的下一行起始位置 然后如果这个位置```i```(起始位置+```cols```)是空格 那么说明下一行的起始位置应该是```i+1```
否则说明它是一个完整的字符被分割了 那么我们需要倒回去找到这个单词的起始点
## Code

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