Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/418.html

418. Sentence Screen Fitting

Level

Medium

Description

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:

  1. A word cannot be split into two lines.
  2. The order of words in the sentence must remain unchanged.
  3. Two consecutive words in a line must be separated by a single space.
  4. Total words in the sentence won’t exceed 100.
  5. Length of each word is greater than 0 and won’t exceed 10.
  6. 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.

Solution

Use dynamic programming. Let the length of sentence be length. Create two arrays dp and next, both of which have length length, where dp[i] represents the number of times the given sentence can be fitted on the screen when starting from the word sentence[i], and next[i] represents the index of the first word in the next line.

For each word in sentence, fill the corresponding values in dp and next. Then for each row, calculate the number of times the given sentence can be fitted on the screen in the row, and the first word in the next row. Finally, return the total number of times the given sentence can be fitted.

  • class Solution {
    public int wordsTyping(String[] sentence, int rows, int cols) {
        int length = sentence.length;
        int[] dp = new int[length];
        int[] next = new int[length];
        for (int i = 0; i < length; i++) {
            int count = 0;
            int index = i;
            int remainWidth = cols;
            while (remainWidth >= sentence[index].length()) {
                remainWidth -= sentence[index].length() + 1;
                index++;
                if (index == length) {
                    count++;
                    index = 0;
                }
            }
            dp[i] = count;
            next[i] = index;
        }
        int screensCount = 0;
        int index = 0;
        for (int i = 0; i < rows; i++) {
            screensCount += dp[index];
            index = next[index];
        }
        return screensCount;
    }
}

  • class Solution(object):
  def wordsTyping(self, sentence, rows, cols):
    """
    :type sentence: List[str]
    :type rows: int
    :type cols: int
    :rtype: int
    """
    s = " ".join(sentence) + " "
    n = len(s)
    start = 0
    for _ in range(rows):
      start += cols - 1
      if s[start % n] == " ":
        start += 1
      elif s[(start + 1) % n] == " ":
        start += 2
      else:
        while start > 0 and s[(start - 1) % n] != " ":
          start -= 1
    return start / n

All Problems

All Solutions