This notebook was prepared by Donne Martin. Source and license info is on GitHub.

Solution Notebook

Problem: Find how many times a sentence can fit on a screen.

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.

Constraints

  • Can we assume sentence is ASCII?
    • Yes
  • Can we assume the inputs are valid?
    • No
  • Is the output an integer?
    • Yes
  • Can we assume this fits memory?
    • Yes

Test Cases

  • None -> TypeError
  • rows < 0 or cols < 0 -> ValueError
  • cols = 0 -> 0
  • sentence = '' -> 0
  • rows = 2, cols = 8, sentence = ["hello", "world"] -> 1
  • rows = 3, cols = 6, sentence = ["a", "bcd", "e"] -> 2
  • rows = 4, cols = 5, sentence = ["I", "had", "apple", "pie"] -> 1

Algorithm

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:

  • Time: O(1)
  • Space: O(1)

Code

In [1]:
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

Unit Test

In [2]:
%%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
In [3]:
%run -i test_count_sentence_fit.py
Success: test_count_sentence_fit