​LeetCode刷題實戰91:解碼方法

算法的重要性，我就不多說了吧，想去大廠，就必須要經過基礎知識和業務邏輯面試+算法面試。所以，為了提高大家的算法能力，這個公眾號後續每天帶大家做一道算法題，題目就從LeetCode上面選 ！

今天和大家聊的問題叫做 解碼方法，我們先來看題面：

https://leetcode-cn.com/problems/decode-ways/

A message containing letters from A-Z is being encoded to numbers using the following mapping:

題意一條包含字母 A-Z 的消息通過以下方式進行了編碼：給定一個只包含數字的非空字符串，請計算解碼方法的總數。

示例 1：

輸入："12"
輸出：2
解釋：它可以解碼為 "AB"（1 2）或者 "L"（12）。

示例 2：

輸入："226"
輸出：3
解釋：它可以解碼為 "BZ" (2 26), "VF" (22 6), 或者 "BBF" (2 2 6) 。

示例 3：

輸入：s = "0"
輸出：0

示例 4：

輸入：s = "1"
輸出：1

示例 5：

輸入：s = "2"
輸出：1

解題https://www.cnblogs.com/techflow/p/13489811.html題解我們觀察一下樣例，比如12可以理解成12這個字符也就是L，也可以理解成1和2兩個字符拼接而成。同樣226有三種還原的方法，分別是(2, 2, 6), (22, 6), (2, 26)。我們只需要返回所有可能的數量即可。這道題看起來沒有頭緒，但是當我們仔細分析一下其中的情況，其實並不複雜。首先對於字符串當中的每一位來說，只有0到9這10種可能性。我們逐一來考慮，首先如果是0，由於我們的A映射的是1，所以0隻能和前面一個數字湊成10或者是20，如果前一位不是1或者是2，那麼說明這個字符串是非法的，也就是沒有辦法還原。如果某一位是1-9當中的數字，它都可以單獨成為一個字母。我們再考慮它的前一位，它的前一位只有1和2這兩種可能可以構成新的組成。這裡要注意，如果它的前一位是2的話，那麼當前位必須要小於6，因為英文字母最多只到26。所以這裡也需要進行一個特殊判斷，除此之外，就沒有其他情況了。這些可能性都列舉出來之後，剩下的就簡單了，比如我們可以用深搜來搜索所有解的可能性。由於我們已經列舉出了所有的情況，所以這段代碼並不難寫，但是想要一次就寫對也不容易。

class Solution:
    def numDecodings(self, s: str) -> int:
        n = len(s)
        ret = 0
        
        def dfs(i):
            nonlocal ret
            
            if i >= n:
                ret += 1
                return 
            
            # 當前位如果是0則說明無解，return
            # 當前位為0說明上一位不是1或者2
            if s[i] == '0':
                return
            
            # 遞歸單個的情況
            dfs(i+1)
            
            # 判斷下一位能否構成組合
            if i+1 < n and (s[i] == '1' or (s[i] == '2' and ord(s[i+1]) <= ord('6'))):
                dfs(i+2)
                
        dfs(0)
        return ret

搜索算法固然可以解，但是一定會超時。這一點也不難想明白，當我們的字符串長度大了之後，帶來的解的可能性是非常多的。最極端的情況下，比如每一位都是1，它都可以單獨作為一個字符也可以和下一位組合成11構成新的字符。這樣的情況總數是以斐波那契數列遞增的，n不需要多大帶來的解的數量就是天文數字了。使用搜索算法我們需要窮舉每一種情況，哪怕尋找每一個解只需要動態規劃。我們分析一下會發現每一位數字能夠組成的解只和它的前一位有關，和後面的都沒有關係。這樣的話顯然是滿足動態規劃的無後效性的。也就是說前面的字符組合的情況不會影響後面的解。我們假設dp[i]存儲的是前i個數字構成的解的數量，對於s[i]來說有10種情況，分別是0到9。如果s[i]為0，那麼s[i-1]如果是1或者是2的話，只有一種情況，就是0和s[i-1]組成10或者是20。那麼dp[i] = dp[i-2]。如果s[i]不為0，那麼s[i]可以選擇單獨成為一個字符，那麼dp[i] = dp[i-1]。當然如果s[i-1]是1或者是2的話，s[i]也可以選擇和s[i-1]合起來組成一個字符。那麼這樣的情況下，dp[i]需要再額外增加dp[i-2]，也就是dp[i]構成的答案可能性增加了。如果把這些狀態之間的轉移情況都梳理清楚了，那麼這個代碼肯定不難寫的。

class Solution:
    def numDecodings(self, s: str) -> int:
        n = len(s)
        # 為了簡化判斷，我們把s前面加上0，這樣字符串下標從1開始
        s = '0' + s
        dp = [0 for _ in range(n+2)]
        
        dp[0] = 1
        for i in range(1, n+1):
            # 如果當前位0，那麼判斷前一位是否是1或2
            # 否則一定無解
            if s[i] == '0':
                if i > 1 and s[i-1] in ('1', '2'):
                    dp[i] = dp[i-2]
                else:
                    return 0
                continue
            dp[i] = dp[i-1]
            # 能和前一位構成字符，那麼加上dp[i-2]的數量
            if i > 1 and s[i-1] == '1' or s[i-1] == '2' and ord(s[i]) <= ord('6'):
                dp[i] += dp[i-2]
        return dp[n]

從動態規劃的角度上來看，這道題並不算困難，說是迎刃而解也不為過。但如果沒有想到動態規劃，糾結於搜索算法的話那麼可能一直都沒有辦法AC。我不清楚給差評的是否都是後一種情況，但單純從題目的質量上來說，這道題的質量是不錯的，是一道很不錯的聯繫動態規劃的習題，因此建議大家有時間都能體會一下。好了，今天的文章就到這裡，如果覺得有所收穫，請順手點個在看或者轉發吧，你們的支持是我最大的動力。