題目出處
難度
medium
個人範例程式碼
MOD_NUM = pow(10, 9)+7
class Solution:
def countTexts(self, pressedKeys: str) -> int:
if not pressedKeys:
return 0
# cur = i = -1, i-1=-2
dp = [1] # init
for i in range(len(pressedKeys)):
dp.append(dp[-1]) # default append last, not same # dp[-1] + a
if i > 0 and pressedKeys[i] == pressedKeys[i-1]: # same 1+1
dp[-1] += dp[-3] # dp[i-2] + b
if i > 1 and pressedKeys[i] == pressedKeys[i-2]: # same 1+2
dp[-1] += dp[-4] # dp[i-3] + c
if i > 2 and pressedKeys[i] in ["7","9"] and pressedKeys[i] == pressedKeys[i-3]: # same 1+3, only 79
dp[-1] += dp[-5] # dp[i-4] + d
dp[-1] %= MOD_NUM
# print(dp)
return dp[-1]
最近在練習程式碼本身就可以自解釋的 Coding style，可以嘗試直接閱讀程式碼理解
算法說明
這題目的圖，是直接拿 leetcode 第 17 題的圖來用的嗎XDD
https://wongwongnotes-github-io.pages.dev/python/leetcode-python-17/
不同的是，這一題比較接近真實使用狀況，
而 17 題只是單純算組合而已。
思考上偏硬的題目，先注意到只有 7, 9 有4個文字需要處理。
我們可以知道:
- 新的下一個字母，都是由「之前全部組合 + 一個新字」
- 當新字為重複時，等同於「之"前前"全部組合 + 兩新字視為一個新字」
… 以此類推
改寫成程式碼變成：
- 新的下一個字母，都是由「之前全部組合 + 一個新字」
dp[i] = dp[i-1] # dp[i-1] + "a"
- 當新字為重複時，等同於「之前前全部組合 + 兩新字視為一個新字」
dp[i] += dp[i-2] # 加上新的可能性，前兩個組合 + 兩個字視為一個新字 (dp[i-2] + "b(aa)")
… 以此類推
(推導可從下圖觀察，過程比較亂一些)
input handling
如果沒有 input ，return 0
Boundary conditions
for loop 控制範圍