Leetcode

Sentence Screen Fitting

May 26, 2022 by aAshish

  • Time:O(|\texttt{rows}| \cdot 10)
  • Space:O(\Sigma |\texttt{sentence[i]}|)

C++

 
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--) {
      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;
  }
};

JAVA

 
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;
  }
}

Python

 
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