Leetcode-91.解码方法

发表于 分类于 阅读次数：

题目链接：https://leetcode-cn.com/problems/decode-ways/

解法1：动态规划

1.dp[i]表示从开始到i位置的解法方法总数

2.设a=s[i-1]+s[i-2]

（1）如果a是0直接返回0，因为若连续两位为0，必然无法进行解码

（2）如果s[i-1]是0，同时a>26，直接返回0.因为这种情况只能s[i-2]和s[i-1]组成一个字母，但数字又大于26，所以无法解码。否则的话dp[i]=dp[i-2]

（3）如果a>26或者a<10则只能让dp[i]=dp[i-1]

（4）其他情况dp[i]=dp[i-1]+dp[i-2]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
public:
    int numDecodings(string s) {
        int n=s.length();
        if(s[0]=='0')
            return 0;
        vector<int> dp(n+1,0);
        dp[0]=1;
        dp[1]=1;
        int a,i;
        for(i=2;i<=n;i++)
        {
            a=(s[i-2]-'0')*10+(s[i-1]-'0');
            cout<<a<<endl;
            if(a==0)
                return 0;
            else if((s[i-1]-'0')==0)
            {
                if(a>26)
                    return 0;
                dp[i]=dp[i-2];
            }
            else if(a>26||a<10)
                dp[i]=dp[i-1];
            else dp[i]=dp[i-1]+dp[i-2];
        }
        return dp[n];
    }
};