dynamicProgramming4

发表于 分类于 ，

题目描述[原题链接][https://leetcode-cn.com/problems/decode-ways/]

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

1
2
3
4
'A' -> 1
'B' -> 2
...
'Z' -> 26

给定一个只包含数字的非空字符串，请计算解码方法的总数。

示例 1:

1
2
3
输入: "12"
输出: 2
解释: 它可以解码为 "AB"（1 2）或者 "L"（12）。

示例 2:

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

算法描述

分三种情况讨论：

- `s[i]=='0'`时，`s[i-1]=='1'`或`s[i-1]=='2'`时，`dp[i]=dp[i-2]`,否则`return 0`;
- `s[i-1]=='1'`时,`dp[i]=dp[i-1]+dp[i-2]`;
- `s[i-1]=='2'`并且`s[i]>='1'&&s[i]<='6'`此时`dp[i]=dp[i-1]+dp[i-2]`;

分析可知，结果只和前两项有关，所以空间复杂度可以从O(n)降到O(1);

C++代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    int numDecodings(string s) {
        if(s[0]=='0')return 0;
        int pre = 1,curr = 1;
        for(int i=1;i<s.size();i++){
            int tmp = curr;
            if(s[i]=='0'){
                if(s[i-1]=='1'||s[i-1] == '2')curr=pre;
                else return 0;
            }else if(s[i-1]=='1'||(s[i-1]=='2'&&s[i]>='1'&&s[i]<='6'))
            {
                curr = tmp+pre;
            }
            pre = tmp;
        }
        return curr;
    }
};

Java代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public int numDecodings(String s) {
        if(s.charAt(0)=='0')return 0;
        int pre =1,curr =1;
        for(int i=1;i<s.length();i++){
            int tmp = curr;
            if(s.charAt(i) == '0'){
                if(s.charAt(i-1)=='1'||s.charAt(i-1)=='2'){
                    curr = pre;
                }
                else return 0;
            }
            else if(s.charAt(i-1)=='1'||(s.charAt(i-1)=='2'&&s.charAt(i)>='1'&&s.charAt(i)<='6')){
                curr = tmp + pre;
            }
            pre = tmp;
        }
        return curr;
    }
}