# 418     Sentence Screen Fitting

## 418. [Sentence Screen Fitting](https://leetcode.com/problems/sentence-screen-fitting/description/)

## 1. Question

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:**

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

## 2. Implementation

思路: 这道题是给定一个每个单词以空格隔开的句子，要求用多少这个句子才能完全fit上 row \* col的screen, 一个单词不能分布在不同的两行。所以我们先得到这个句子用空格隔开后的长度len，然后用start这个变量判断每行最后一个空格在哪，最后的结果就是start / len

```java
class Solution {
    public int wordsTyping(String[] sentence, int rows, int cols) {
        String s = "";

        for (String word : sentence) {
            s += word + " ";
        }

        int len = s.length();
        int start = 0;

        for (int i = 0; i < rows; i++) {
            start += cols;
            if (s.charAt(start % len) == ' ') {
                ++start;
            }
            else {
                while (start > 0 && s.charAt((start - 1) % len) != ' ') {
                    --start;
                }
            }
        }
        return start / len;
    }
}
```

## 3. Time & Space Complexity

时间复杂度O(n), 空间复杂度O(n)


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://protegejj.gitbook.io/algorithm-practice/leetcode/dynamic-programming/418-sentence-screen-fitting.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.