Sentence Screen Fitting — LeetCode 418 Python Solution

The problem

Given a rows x cols screen and a sentence represented as a list of strings, return the number of times the given sentence can be fitted on the screen. The order of words in the sentence must remain unchanged, and a word cannot be split into two lines.

Example

Input

sentence = ["hello","world"], rows = 2, cols = 8

Output

1

Explanation

hello---

Python solution

class Solution:
    def wordsTyping(self, sentence: List[str], rows: int, cols: int) -> int:
        s = " ".join(sentence) + " "
        m = len(s)
        cur = 0
        for _ in range(rows):
            cur += cols
            if s[cur % m] == " ":
                cur += 1
            while cur and s[(cur - 1) % m] != " ":
                cur -= 1
        return cur // m

Complexity

Pattern: Dynamic Programming

Define a state, write the transition, and stop recomputing the same subproblem. LeetCode 418. Sentence Screen Fitting is filed here on both counts: the reference solution below belongs to the algorithm family this hub collects, and LeetCode tags it Dynamic Programming.

The dynamic programming guide has the Python template for the pattern and the 481 LeetCode problems that use it.

Related problems