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
- Join the sentence into one string with a trailing space and imagine laying it across an infinite sequence of rows.
- Track
pos, the character index in that repeated string where the current row begins. - Advance a row with
pos += cols, then step back to the start of the word that got cut, and finally step past the space. - 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 ispos // 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.