Skip to content

418. Sentence Screen Fitting

  • Time: $O(|\texttt{rows}| \cdot 10)$
  • Space: $O(\Sigma |\texttt{sentence[i]}|)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
 public:
  int wordsTyping(vector<string>& sentence, int rows, int cols) {
    const string& combined = getCombined(sentence);
    const int n = combined.length();
    int i = 0;  // (i % n) points to the index of combined in each row

    while (rows-- > 0) {
      i += cols;
      if (combined[i % n] == ' ') {
        ++i;
      } else {
        while (i > 0 && combined[(i - 1) % n] != ' ')
          --i;
      }
    }

    return i / n;
  }

 private:
  string getCombined(const vector<string>& sentence) {
    string combined;
    for (const string& word : sentence)
      combined += (word + ' ');
    return combined;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
class Solution {
  public int wordsTyping(String[] sentence, int rows, int cols) {
    final String combined = String.join(" ", sentence) + " ";
    final int n = combined.length();
    int i = 0; // (i % n) points to the index of combined in each row

    while (rows-- > 0) {
      i += cols;
      if (combined.charAt(i % n) == ' ') {
        ++i;
      } else {
        while (i > 0 && combined.charAt((i - 1) % n) != ' ')
          --i;
      }
    }

    return i / n;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
class Solution:
  def wordsTyping(self, sentence: list[str], rows: int, cols: int) -> int:
    combined = ' '.join(sentence) + ' '
    n = len(combined)
    i = 0

    for _ in range(rows):
      i += cols
      if combined[i % n] == ' ':
        i += 1
      else:
        while i > 0 and combined[(i - 1) % n] != ' ':
          i -= 1

    return i // n