# Python solution with detailed explanation

• Solution

Sentence Screen Fitting https://leetcode.com/problems/sentence-screen-fitting/

Caching Solution - TLE

• The first approach is to fit word by word of the sentence. build_sentence takes a starting column id and fills out the entire sentence. It returns the next_col_id and the row offset required to fill the sentence.
• Now once we get the new row offset, we test if the additional sentence will fit in our matrix or not - i.e. do we have sufficient rows to fill it or not?
• In addition, we cache the offset and new col_id, so that the next time the pattern repeats, we dont need to recompute.
``````class Solution1(object):
def build_sentence(self, sentence, col_id, cols):
row, i = 0, 0
while i < len(sentence):
x = len(sentence[i])
if x + col_id <= cols:
i += 1
col_id += x
(col_id, row) = (0, row + 1) if col_id == cols or col_id + 1 == cols else (col_id + 1, row)
else:
col_id, row = 0, row+1
return (col_id, row)

def wordsTyping(self, sentence, rows, cols):
"""
:type sentence: List[str]
:type rows: int
:type cols: int
:rtype: int
"""
if any(map(lambda x: len(x) > cols, sentence)):
return 0
row_id, col_id = 0, 0
i, sc = 0, 0
cache = {}
while True:
if col_id not in cache:
cache[col_id] = self.build_sentence(sentence, col_id, cols)
(col_id, offset) = cache[col_id]
row_id += offset
if row_id < rows:
sc += 1
elif row_id == rows and col_id == 0:
sc += 1
break
else:
break
return sc
``````

Optimized Solution

• Iterate over every possible row
• Try to fill the row's columns with as many sentence characters as possible.
• Test the next character in sentence after filling cols character. Use modulo operator for this.
• If this is an " " string, then we are good. Otherwise move back till we get a " ".
• Now increment valid_ch_count by 1 to account for this " "
• Run the code for corner cases: s = "abc de " and col = 7. valid_ch_cnt = (0+7) = 7. This points to 7%7 or s[0]. So we move back 1 and valid_ch_cnt becomes 6 and will point to last character which is " ". Then we increment to include this charcater.
• Similarly run a case for s = "abc de " and row=2 and col = 6. Notice that "abc de" aligns with the column boundary. But the valid_ch_count is still 7 after first row. In the second row, we have valid_ch_count as 7 + 6 = 13. Finally it turns out to be 14 and 14/7 = 2. Notice we do not take a modulo with cols, but with len(s) and hence get the right answer.
• This artimetic makes sure that valid_ch_count // len(s) gives the right answer.
``````class Solution(object):
def wordsTyping(self, sentence, rows, cols):
"""
:type sentence: List[str]
:type rows: int
:type cols: int
:rtype: int
"""
s, valid_ch_cnt = " ".join(sentence) + " ", 0
for i in range(rows):
valid_ch_cnt += cols
while s[valid_ch_cnt%len(s)] != " ":
valid_ch_cnt -= 1
valid_ch_cnt += 1 # Add the empty space to count of valid characters
return valid_ch_cnt // len(s)
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.