91. 解码方法

一条包含字母 A-Z 的消息通过以下方式进行了编码：

‘A’ -> 1
‘B’ -> 2
…
‘Z’ -> 26
给定一个只包含数字的非空字符串，请计算解码方法的总数。

示例 1:

输入: “12”
输出: 2
解释: 它可以解码为 “AB”（1 2）或者 “L”（12）。
示例 2:

输入: “226”
输出: 3
解释: 它可以解码为 “BZ” (2 26), “VF” (22 6), 或者 “BBF” (2 2 6) 。

【中等】
【分析】动态规划。
每次走1步或者2步，联想到斐波那契数列f(n)=f(n-1)+f(n-2)。

1. s[i-1]='1',s[i]无论是什么都可以：dp[i]=dp[i-1]+dp[i-2] ，因为如果s[i-1],s[i]合并在一起解码，那么译法是确定的，不增加解码方法，此时方法有dp[i-2]种；如果s[i-1],s[i]分开解码，此时方法有dp[i-1]种。
2. s[i-1]='2',0<=s[i]<=6时dp[i]=dp[i-1]+dp[i-2]；否则dp[i]=dp[i-1]。因为若s[i]>7那么s[i]的译法是确定的，因而dp[i]与s[i]无关。
3. s[i]='0',s[i-1]=1 or 2 时，译法确定，dp[i]与dp[i-1]无关，此时，dp[i]=dp[i-2]，否则return 0

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

---

注：回溯法超时
s="4757562545844617494555774581341211511296816786586787755257741178599337186486723247528324612117156948"时用回溯法超时了。。。。简单说一下回溯的思路。

循环利用的是1个字符或者2个字符来遍历s的，所以超时也是必然。。。

在循环遍历s时，注意1.int(s[i:i+k]): [1,26],其中k:[1,2],i:[0,len(s)-1]；注意2. 当k==2 and s[i]=="0"时，说明子字符串是“01”~“09”之类的，不符合要求，所以要continue掉。

class Solution(object):
    n=0
    def numDecodings(self, s):
        """
        :type s: str
        :rtype: int
        """
        self.decoding(s,0)
        return self.n
        
    def decoding(self,s,i):
        if i==len(s):
            self.n+=1
            return
        for k in range(1,3):
            if i+k<=len(s) and int(s[i:i+k])>0 and int(s[i:i+k])<=26:
                if k==2 and s[i]=="0":
                    continue
                self.decoding(s,i+k)
            else:
                continue

path版本：

        res=[];path=[];index=0;i=0;
        decoding(s,res,path,i,seen)
        res
        
    def decoding(s,index,res,path,i,seen):
        if index==len(s):
            res.append(path[:])
            return
        for k in range(1,3):
            if i+k<=len(s) and int(s[i:i+k])>0 and int(s[i:i+k])<=26:
                if k==2 and s[i]=="0":
                    continue
                path.append(s[i:i+k])
                decoding(s,index+k,res,path,i+k)
                path.pop()
            else:
                continue