程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> LeetCode Decode Ways

LeetCode Decode Ways

編輯:C++入門知識

LeetCode Decode Ways


LeetCode解題之Decode Ways


原題

現在有如下的字母與數字的對應關系:1-A, 2-B, …26-Z。給定一個由數字組成的字符串,判斷按照上面的映射可以轉換成多少種不同的字符串。

注意點:

如果字符不能正常轉換,如”70”,那麼返回0

例子:

輸入: s = “12”

輸出: 2(包括”AB”(1 2)和”L”(12))

解題思路

第一感覺就是動態規劃,先寫了一個從前往後的版本,要復雜的分類要論,代碼很亂,後來發現從後開始遍歷更加容易。來看一下遞推式,假設原先的字符串為”y231”,現在在它之前加一個數字得到”xy231”,如果x不為0,此時,如果”xy”不在1-26之間,那麼原先能轉換的種類不變,只是在每個字符串之前增加一個x轉換後的字母;如果”xy”在1-26之間,那麼除了在原先每個字符串之前增加x轉換後的字母,還可能是在”231”轉化之後的字符串前增加”xy”轉化的字母。那如果x等於0呢,此時是一個非法字符串,讓它默認為0。但不能跳出循環,因為在前面繼續增加數字可能將字符串變為合法的。

AC源碼

class Solution(object):
    def numDecodings(self, s):
        """
        :type s: str
        :rtype: int
        """
        length = len(s)
        if length == 0:
            return 0
        dp = [0 for __ in range(length + 1)]
        dp[length] = 1
        dp[length - 1] = 1 if s[length - 1] != '0' else 0
        for i in range(length - 2, -1, -1):
            if s[i] != '0':
                dp[i] = dp[i + 1] + dp[i + 2] if int(s[i:i + 2]) <= 26 else dp[i + 1]
        return dp[0]


if __name__ == "__main__":
    assert Solution().numDecodings("110") == 1
    assert Solution().numDecodings("40") == 0

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved