美文网首页
91. Decode Ways

91. Decode Ways

作者: xiaoyaook | 来源:发表于2017-12-11 18:12 被阅读0次

    动态规划问题
    创建一个长度为n+1的数组来储存子问题的结果.
    状态转移方程:
    dp[i] =
    dp[i-1]
    当s[i] != "0"
    +dp[i-2] 当"09" < s[i-1:i+1] < "27"
    数组最后一个数即为返回的结果.
    基础情况:
    dp[0] = 1表示一个空字符串只有一种方式去decode
    当字符串的第一个字符不为0时,dp[1]为1,否则为0.

    class Solution(object):
        def numDecodings(self, s):
            """
            :type s: str
            :rtype: int
            """
            if s == '':
                return 0
            dp = [0 for x in range(len(s)+1)]
            dp[0] = 1
            for i in range(1, len(s)+1):
                if s[i-1] != "0":
                    dp[i] += dp[i-1]
                if i != 1 and s[i-2:i] < "27" and s[i-2:i] > "09":
                    dp[i] += dp[i-2]
            return dp[-1]
    

    相关文章

      网友评论

          本文标题:91. Decode Ways

          本文链接:https://www.haomeiwen.com/subject/jexwixtx.html