題目出處

91. Decode Ways

難度

medium

個人範例程式碼

class Solution:
    def numDecodings(self, s: str) -> int:
        if not s:
            return 0

        if s[0] == "0":
            return 0

        # dp[i] = (dp[i-1], contain this word) + (dp[i-1], contain two word)
        dp = [1, 1]

        for i, c in enumerate(s):
            ans_contain_this_word = 0
            if self.is_valid(s[i]): # dp[i-1] + i, check if 0
                ans_contain_this_word += (dp[-1])

            if i > 0 and self.is_valid_2(s[i-1:i+1]): # dp[i-2] + i-1,i
                ans_contain_this_word += (dp[-2])

            dp.append(ans_contain_this_word)

        return dp[-1]

    def is_valid_2(self, s):
        if s[0] == 0:
            return False

        return 10 <= int(s) <= 26

    def is_valid(self, s):
        return 1 <= int(s) <= 9

最近在練習程式碼本身就可以自解釋的 Coding style，可以嘗試直接閱讀程式碼理解

算法說明

類似 fibonacci 數列的題目，這樣就是要用 dp 去解啦!

• dp[i] = (dp[i-1], 現在數字) + (dp[i-2], 最後兩位數字)

• dp[i-1] 我們去確認現在數字是否 1~9，排除 0

• dp[i-2] 我們去確認是否兩位數字介於 10~26，排除 0 開頭與其他不符合規則的數字

input handling

• 處理沒有 s 或是「 s 以 0 為開頭的情況」， return 0

Boundary conditions

控制 for-loop 的範圍

Reference

• 解码方法 · Decode Ways