Question

418. Sentence Screen Fitting

中文文档

Description

Given a rows x cols screen and a sentence represented as a list of strings, return _the number of times the given sentence can be fitted on the screen_.

The order of words in the sentence must remain unchanged, and a word cannot be split into two lines. A single space must separate two consecutive words in a line.

 

Example 1:

Input: sentence = ["hello","world"], rows = 2, cols = 8
Output: 1
Explanation:
hello---
world---
The character '-' signifies an empty space on the screen.

Example 2:

Input: sentence = ["a", "bcd", "e"], rows = 3, cols = 6
Output: 2
Explanation:
a-bcd- 
e-a---
bcd-e-
The character '-' signifies an empty space on the screen.

Example 3:

Input: sentence = ["i","had","apple","pie"], rows = 4, cols = 5
Output: 1
Explanation:
i-had
apple
pie-i
had--
The character '-' signifies an empty space on the screen.

 

Constraints:

• 1 <= sentence.length <= 100
• 1 <= sentence[i].length <= 10
• sentence[i] consists of lowercase English letters.
• 1 <= rows, cols <= 2 * 104

Solutions

Solution 1

class Solution:
  def wordsTyping(self, sentence: List[str], rows: int, cols: int) -> int:
    s = " ".join(sentence) + " "
    m = len(s)
    cur = 0
    for _ in range(rows):
      cur += cols
      if s[cur % m] == " ":
        cur += 1
      while cur and s[(cur - 1) % m] != " ":
        cur -= 1
    return cur // m

class Solution {
  public int wordsTyping(String[] sentence, int rows, int cols) {
    String s = String.join(" ", sentence) + " ";
    int m = s.length();
    int cur = 0;
    while (rows-- > 0) {
      cur += cols;
      if (s.charAt(cur % m) == ' ') {
        ++cur;
      } else {
        while (cur > 0 && s.charAt((cur - 1) % m) != ' ') {
          --cur;
        }
      }
    }
    return cur / m;
  }
}

class Solution {
public:
  int wordsTyping(vector<string>& sentence, int rows, int cols) {
    string s;
    for (auto& t : sentence) {
      s += t;
      s += " ";
    }
    int m = s.size();
    int cur = 0;
    while (rows--) {
      cur += cols;
      if (s[cur % m] == ' ') {
        ++cur;
      } else {
        while (cur && s[(cur - 1) % m] != ' ') {
          --cur;
        }
      }
    }
    return cur / m;
  }
};

func wordsTyping(sentence []string, rows int, cols int) int {
  s := strings.Join(sentence, " ") + " "
  m := len(s)
  cur := 0
  for i := 0; i < rows; i++ {
    cur += cols
    if s[cur%m] == ' ' {
      cur++
    } else {
      for cur > 0 && s[(cur-1)%m] != ' ' {
        cur--
      }
    }
  }
  return cur / m
}

function wordsTyping(sentence: string[], rows: number, cols: number): number {
  const s = sentence.join(' ') + ' ';
  let cur = 0;
  const m = s.length;
  for (let i = 0; i < rows; ++i) {
    cur += cols;
    if (s[cur % m] === ' ') {
      ++cur;
    } else {
      while (cur > 0 && s[(cur - 1) % m] !== ' ') {
        --cur;
      }
    }
  }
  return Math.floor(cur / m);
}