⚡Flashcard Drill➔
NeetCode #697LC-418Medium1-D Dynamic Programming
← Back to All Problems

#697 · #418 · Sentence Screen Fitting(屏幕可显示句子的数量)

📌 Problem Statement & Constraints

Given sentence (a list of words) and a screen with rows rows and cols columns, count how many times the sentence can be repeated by filling the screen row by row. Words are separated by a single space and a word may never be split across two rows. Constraints: 1 <= sentence.length <= 100, 1 <= rows, cols <= 2 * 10^4, 1 <= sentence[i].length <= 100.

💡 Core Algorithmic Approaches

  1. Join the sentence into one string with a trailing space and imagine laying it across an infinite sequence of rows.
  2. Track pos, the character index in that repeated string where the current row begins.
  3. Advance a row with pos += cols, then step back to the start of the word that got cut, and finally step past the space.
  4. The number of complete repetitions is pos // len(s).

💻 Benchmark Python3 Implementation

class Solution:
    def wordsTyping(self, sentence: List[str], rows: int, cols: int) -> int:
        s = " ".join(sentence) + " "     # trailing space simplifies the wrap
        n = len(s)
        pos = 0                          # char index in the infinitely repeated s
        for _ in range(rows):
            pos += cols
            while s[pos % n] != " ":
                pos -= 1                 # back up to the start of the cut word
            pos += 1                     # move past the space
        return pos // n

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(rows * L): each row backtracks at most one word length L <= 100.
💾 Space Complexity
O(1) beyond the joined string.

⚠️ Interview Pitfalls & Follow-ups

  • Splitting a word across rows: the backtracking loop enforces whole-word placement.
  • Omitting the trailing space: appending one space after the last word makes the modulo indexing uniform; without it the wrap logic breaks.
  • Dividing by cols: the answer counts full sentences, so it is pos // len(s).
  • Assuming every row ends on a space: the modulo index may land mid-word, which is exactly why the while loop exists.
  • Ignoring a word longer than cols: such a word can never fit; the constraints imply every word fits, but the loop would otherwise run off.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🎯 Drill This Card Now➔

🧩 Related 1-D Dynamic Programming Problems