【Leetcode解題】38. Count and Say

題目

• 題目連結
• 目標函式 : countAndSay(n)
  • Input : n: int
  • Output : str

解題概念

• 題意 :
  • countAndSay(1) = 1
  • countAndSay(n) = 計算 countAndSay(n-1)，並將其「說」出來
• 如何「說」出一字串之舉例 :
  1. 假設 a = 3322251
  2. 而須把 a 視為由「2個3, 3個2, 1個5, 1個1」組成
  3. 接著將這些元素合併成 23321511，即為「說」出 a 之結果

我的寫法

• 想法 : 使用遞迴 + for 迴圈
  1. last : 上個讀取的字元、times : last 字元重複的次數
  2. 計算 countAndSay(n-1)，並將其切割成字元陣列 str_list
  3. 依序讀取 str_list中的元素，並有以下兩種狀況 :
     1. 若 當前讀取的字元 == last :
        • 則 times + 1
     2. 若 當前讀取的字元 != last :
        • times + 1 後，將該字元之結果與次數加到 res 中
        • reset 參數 : last 與 times
• 程式碼 :

  if n == 1:
      return "1"
      
  str_list = list(self.countAndSay(n-1))
  last = ""
  res = ""
  times = 0
  for s in str_list:
      # 狀況 1
      if s == last:
          times += 1
      # 狀況 2
      else:
          if times != 0:
              res += (str(times) + last)
          # Reset 參數
          times = 1
          last = s
  res += (str(times) + last)
  return res

• 成效 :
  • Time Complexity: $O(n)$
  • Runtime: 30 ms (faster than 95.78%)
  • Memory Usage: 13.5 M (less than 68.72%)

解答 or 其他優秀寫法

• 其他優秀寫法都用遞迴 + 雙重迴圈，時間與空間複雜度也沒有比較佳