This notebook was prepared by Donne Martin. Source and license info is on GitHub.
See the LeetCode problem page.
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: A word cannot be split into two lines. The order of words in the sentence must remain unchanged. Two consecutive words in a line must be separated by a single space. Total words in the sentence won't exceed 100. Length of each word is greater than 0 and won't exceed 10. 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.
It can be relatively straightforward to come up with the brute force solution, check out the method count_sentence_fit_brute_force
below.
The optimized solutions is discussed in more depth here.
rows = 4 cols = 6 sentence = ['abc', 'de', 'f'] "abc de f abc de f abc de f ..." // start=0 012345 // start=start+cols+adjustment=0+6+1=7 (1 space removed in screen string) 012345 // start=7+6+0=13 012345 // start=13+6-1=18 (1 space added) 012345 // start=18+6+1=25 (1 space added) 012345
Complexity:
class Solution(object):
def count_sentence_fit_brute_force(self, sentence, rows, cols):
if sentence is None:
raise TypeError('sentence cannot be None')
if rows is None or cols is None:
raise TypeError('rows and cols cannot be None')
if rows < 0 or cols < 0:
raise ValueError('rows and cols cannot be negative')
if cols == 0 or not sentence:
return 0
curr_row = 0
curr_col = 0
count = 0
while curr_row < cols:
for word in sentence:
# If the current word doesn't fit on the current line,
# move to the next line
if len(word) > cols - curr_col:
curr_col = 0
curr_row += 1
# If we are beyond the number of rows, return
if curr_row >= rows:
return count
# If the current word fits on the current line,
# 'insert' it here
if len(word) <= cols - curr_col:
curr_col += len(word) + 1
# If it still doesn't fit, then the word is too long
# and we should just return the current count
else:
return count
count += 1
return count
def count_sentence_fit(self, sentence, rows, cols):
if sentence is None:
raise TypeError('sentence cannot be None')
if rows is None or cols is None:
raise TypeError('rows and cols cannot be None')
if rows < 0 or cols < 0:
raise ValueError('rows and cols cannot be negative')
if cols == 0 or not sentence:
return 0
string = ' '.join(sentence) + ' '
start = 0
str_len = len(string)
for row in range(rows):
start += cols
# We don't need extra space for the current row
if string[start % str_len] == ' ':
start += 1
# The current row can't fit, so we'll need to
# remove characters from the next word
else:
while (start > 0 and string[(start - 1) % str_len] != ' '):
start -= 1
return start // str_len
%%writefile test_count_sentence_fit.py
import unittest
class TestSolution(unittest.TestCase):
def test_count_sentence_fit(self):
solution = Solution()
self.assertRaises(TypeError, solution.count_sentence_fit,
None, None, None)
self.assertRaises(ValueError, solution.count_sentence_fit,
'abc', rows=-1, cols=-1)
sentence = ["hello", "world"]
expected = 1
self.assertEqual(solution.count_sentence_fit(sentence, rows=2, cols=8),
expected)
sentence = ["a", "bcd", "e"]
expected = 2
self.assertEqual(solution.count_sentence_fit(sentence, rows=3, cols=6),
expected)
sentence = ["I", "had", "apple", "pie"]
expected = 1
self.assertEqual(solution.count_sentence_fit(sentence, rows=4, cols=5),
expected)
print('Success: test_count_sentence_fit')
def main():
test = TestSolution()
test.test_count_sentence_fit()
if __name__ == '__main__':
main()
Overwriting test_count_sentence_fit.py
%run -i test_count_sentence_fit.py
Success: test_count_sentence_fit