{
"cells": [
{
"cell_type": "markdown",
"metadata": {},
"source": [
"This notebook was prepared by [Donne Martin](https://github.com/donnemartin). Source and license info is on [GitHub](https://github.com/donnemartin/interactive-coding-challenges)."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# Solution Notebook"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Problem: Find how many times a sentence can fit on a screen.\n",
"\n",
"See the [LeetCode](https://leetcode.com/problems/sentence-screen-fitting/) problem page.\n",
"\n",
"\n",
"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.\n",
"\n",
"Note:\n",
"\n",
"A word cannot be split into two lines.\n",
"The order of words in the sentence must remain unchanged.\n",
"Two consecutive words in a line must be separated by a single space.\n",
"Total words in the sentence won't exceed 100.\n",
"Length of each word is greater than 0 and won't exceed 10.\n",
"1 ≤ rows, cols ≤ 20,000.\n",
"Example 1:\n",
"\n",
"Input:\n",
"rows = 2, cols = 8, sentence = [\"hello\", \"world\"]\n",
"\n",
"Output: \n",
"1\n",
"\n",
"Explanation:\n",
"hello---\n",
"world---\n",
"\n",
"The character '-' signifies an empty space on the screen.\n",
"Example 2:\n",
"\n",
"Input:\n",
"rows = 3, cols = 6, sentence = [\"a\", \"bcd\", \"e\"]\n",
"\n",
"Output: \n",
"2\n",
"\n",
"Explanation:\n",
"a-bcd- \n",
"e-a---\n",
"bcd-e-\n",
"\n",
"The character '-' signifies an empty space on the screen.\n",
"Example 3:\n",
"\n",
"Input:\n",
"rows = 4, cols = 5, sentence = [\"I\", \"had\", \"apple\", \"pie\"]\n",
"\n",
"Output: \n",
"1\n",
"\n",
"Explanation:\n",
"I-had\n",
"apple\n",
"pie-I\n",
"had--\n",
"\n",
"The character '-' signifies an empty space on the screen.\n",
"\n",
"\n",
"* [Constraints](#Constraints)\n",
"* [Test Cases](#Test-Cases)\n",
"* [Algorithm](#Algorithm)\n",
"* [Code](#Code)\n",
"* [Unit Test](#Unit-Test)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Constraints\n",
"\n",
"* Can we assume sentence is ASCII?\n",
" * Yes\n",
"* Can we assume the inputs are valid?\n",
" * No\n",
"* Is the output an integer?\n",
" * Yes\n",
"* Can we assume this fits memory?\n",
" * Yes"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Test Cases\n",
"\n",
"* None -> TypeError\n",
"* rows < 0 or cols < 0 -> ValueError\n",
"* cols = 0 -> 0\n",
"* sentence = '' -> 0\n",
"* rows = 2, cols = 8, sentence = [\"hello\", \"world\"] -> 1\n",
"* rows = 3, cols = 6, sentence = [\"a\", \"bcd\", \"e\"] -> 2\n",
"* rows = 4, cols = 5, sentence = [\"I\", \"had\", \"apple\", \"pie\"] -> 1"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Algorithm\n",
"\n",
"It can be relatively straightforward to come up with the brute force solution, check out the method `count_sentence_fit_brute_force` below. \n",
"\n",
"The optimized solutions is discussed in more depth [here](https://discuss.leetcode.com/topic/62455/21ms-18-lines-java-solution/25).\n",
"\n",
"\n",
"rows = 4\n",
"cols = 6\n",
"sentence = ['abc', 'de', 'f']\n",
"\n",
"\"abc de f abc de f abc de f ...\" // start=0\n",
" 012345 // start=start+cols+adjustment=0+6+1=7 (1 space removed in screen string)\n",
" 012345 // start=7+6+0=13\n",
" 012345 // start=13+6-1=18 (1 space added)\n",
" 012345 // start=18+6+1=25 (1 space added)\n",
" 012345\n",
"\n",
"\n",
"Complexity:\n",
"* Time: O(1)\n",
"* Space: O(1)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Code"
]
},
{
"cell_type": "code",
"execution_count": 1,
"metadata": {},
"outputs": [],
"source": [
"class Solution(object):\n",
"\n",
" def count_sentence_fit_brute_force(self, sentence, rows, cols):\n",
" if sentence is None:\n",
" raise TypeError('sentence cannot be None')\n",
" if rows is None or cols is None:\n",
" raise TypeError('rows and cols cannot be None')\n",
" if rows < 0 or cols < 0:\n",
" raise ValueError('rows and cols cannot be negative')\n",
" if cols == 0 or not sentence:\n",
" return 0\n",
" curr_row = 0\n",
" curr_col = 0\n",
" count = 0\n",
" while curr_row < cols:\n",
" for word in sentence:\n",
" # If the current word doesn't fit on the current line,\n",
" # move to the next line\n",
" if len(word) > cols - curr_col:\n",
" curr_col = 0\n",
" curr_row += 1\n",
" # If we are beyond the number of rows, return\n",
" if curr_row >= rows:\n",
" return count\n",
" # If the current word fits on the current line,\n",
" # 'insert' it here\n",
" if len(word) <= cols - curr_col:\n",
" curr_col += len(word) + 1\n",
" # If it still doesn't fit, then the word is too long\n",
" # and we should just return the current count\n",
" else:\n",
" return count\n",
" count += 1\n",
" return count\n",
"\n",
" def count_sentence_fit(self, sentence, rows, cols):\n",
" if sentence is None:\n",
" raise TypeError('sentence cannot be None')\n",
" if rows is None or cols is None:\n",
" raise TypeError('rows and cols cannot be None')\n",
" if rows < 0 or cols < 0:\n",
" raise ValueError('rows and cols cannot be negative')\n",
" if cols == 0 or not sentence:\n",
" return 0\n",
" string = ' '.join(sentence) + ' '\n",
" start = 0\n",
" str_len = len(string)\n",
" for row in range(rows):\n",
" start += cols\n",
" # We don't need extra space for the current row\n",
" if string[start % str_len] == ' ':\n",
" start += 1\n",
" # The current row can't fit, so we'll need to \n",
" # remove characters from the next word\n",
" else:\n",
" while (start > 0 and string[(start - 1) % str_len] != ' '):\n",
" start -= 1\n",
" return start // str_len"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Unit Test"
]
},
{
"cell_type": "code",
"execution_count": 2,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"Overwriting test_count_sentence_fit.py\n"
]
}
],
"source": [
"%%writefile test_count_sentence_fit.py\n",
"import unittest\n",
"\n",
"\n",
"class TestSolution(unittest.TestCase):\n",
"\n",
" def test_count_sentence_fit(self):\n",
" solution = Solution()\n",
" self.assertRaises(TypeError, solution.count_sentence_fit, \n",
" None, None, None)\n",
" self.assertRaises(ValueError, solution.count_sentence_fit, \n",
" 'abc', rows=-1, cols=-1)\n",
" sentence = [\"hello\", \"world\"]\n",
" expected = 1\n",
" self.assertEqual(solution.count_sentence_fit(sentence, rows=2, cols=8),\n",
" expected)\n",
" sentence = [\"a\", \"bcd\", \"e\"]\n",
" expected = 2\n",
" self.assertEqual(solution.count_sentence_fit(sentence, rows=3, cols=6),\n",
" expected)\n",
" sentence = [\"I\", \"had\", \"apple\", \"pie\"]\n",
" expected = 1\n",
" self.assertEqual(solution.count_sentence_fit(sentence, rows=4, cols=5),\n",
" expected)\n",
" print('Success: test_count_sentence_fit')\n",
"\n",
"\n",
"def main():\n",
" test = TestSolution()\n",
" test.test_count_sentence_fit()\n",
"\n",
"\n",
"if __name__ == '__main__':\n",
" main()"
]
},
{
"cell_type": "code",
"execution_count": 3,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"Success: test_count_sentence_fit\n"
]
}
],
"source": [
"%run -i test_count_sentence_fit.py"
]
}
],
"metadata": {
"kernelspec": {
"display_name": "Python 3",
"language": "python",
"name": "python3"
},
"language_info": {
"codemirror_mode": {
"name": "ipython",
"version": 3
},
"file_extension": ".py",
"mimetype": "text/x-python",
"name": "python",
"nbconvert_exporter": "python",
"pygments_lexer": "ipython3",
"version": "3.7.2"
}
},
"nbformat": 4,
"nbformat_minor": 1
}