leetcode_[python/C++]_91_Decode Ways_動态規劃

題目連結

【題目】

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

‘A’ -> 1

‘B’ -> 2

…

‘Z’ -> 26

Given an encoded message containing digits, determine the total number of ways to decode it.

For example,

Given encoded message “12”, it could be decoded as “AB” (1 2) or “L” (12).

The number of ways decoding “12” is 2.

【解析】

采用動态規劃的方法。

網上有空間複雜度為O（n）的做法比如：

class Solution {
public:
    int numDecodings(string s) {
        if (s.empty() || (s.size() >  && s[] == '0')) return ;
        vector<int> dp(s.size() + , );
        dp[] = ;
        for (int i = ; i < dp.size(); ++i) {
            dp[i] = (s[i - ] == '0') ?  : dp[i - ];
            if (i >  && (s[i - ] == '1' || (s[i - ] == '2' && s[i - ] <= '6'))) {
                dp[i] += dp[i - ];
            }
        }
        return dp.back();
    }
};
           

這裡采用一種空間複雜度為O(1)的方法（AC）【很快】：

兩個變量p1,p2

初始為1

1）當s[i]==’0’時候，p1 = 0

2）當s[i] !=’0’時候，則當s[i-1]==’1’或者s[i-1]==’2’且s[i-1]<=’6’時候，p1 = p1 + p2（相當于加上前面的總數，p2記錄上一次的總數）

p2 = p1 - p2（其實就是p2等于之前的p1）

3）否則，p2 = p1

class Solution {
public:
    int numDecodings(string s) {
        if(s[] == '0' || s.length() == ) return ;
        int p1=,p2=;
        for(int i=;i<s.length();i++){
            if(s[i] == '0') p1 = ;
            if(s[i-] == '1' || s[i-] == '2' && s[i] <= '6'){
                p1 = p2 + p1;
                p2 = p1 - p2;
            }
            else p2 = p1;
        }
        return p1;
    }
};
           

python

(1)

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

(2)

class Solution(object):
    def numDecodings(self, s):
        if (len(s) ==  or s[] == '0'):
            return 
        p1 = 
        p2 = 
        for i in range(,len(s)):
            if s[i] == '0':
                p1 = 
            if s[i-] == '1' or (s[i-] == '2' and s[i] <= '6'):
                p1 = p1 + p2
                p2 = p1 - p2
            else:
                p2 = p1
        return p1