{ "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",
"apple\n",
"pie-I\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 }