Leetcode # 418. Sentence Screen Fitting

https://leetcode.com/problems/sentence-screen-fitting

Solution

Time Complexity: O(rows * cols)
Space Complexity: O(1)
(The input and output generally do not count towards the space complexity.)

class Solution:
  def wordsTyping(self, sentence: List[str], rows: int, cols: int) -> int:
    i = j = p = times = 0
    full_len = sum([len(w) for w in sentence]) + len(sentence) - 1
    record = {
      0:[0, 0]
    }
    while i < rows:
      if times > 0 and p in record:
        t = (rows - i) // (i - record[p][0])
        times += (times - record[p][1]) * t
        i += (i - record[p][0]) * t
        if i >= rows:
          break
      record[p] = [i, times]
      if p == 0 and j + full_len <= cols:
        t = (cols - j + 1) // (full_len + 1)
        times += t
        j += t * (full_len + 1)
      
      while j + len(sentence[p]) <= cols:
        # line += sentence[p] + " "
        j += len(sentence[p]) + 1
        p += 1
        if p == len(sentence):
          times += 1
          p = 0
      i += 1
      j = 0
          
    return times

注意點

• 注意 sentence 內的單詞間，
  用做間隔的空白造成的影響
• 用迴圈去一個一個計算，會造成 Time Limit Exceeded
  • 當一個 row 足夠長到讓你可以放入整個 sentence 時
    應該省略使用迴圈去一個一個計算 sentence[p]
  • 當你換行後，發現 sentence 的指標 p 和之前一樣
    表示開始重複了，應使用重複的那幾行去填充之後的空間
    （ record 用以記錄前面每一行起始時的狀態）

Last Updated on 2023/08/16 by A1go