解码方法

来源Leetcode第91题解码方法

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

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

示例 1:

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

---

自顶向下动态规划

一开始从前往后推的动态规划写错了，在处理当前位为“0”时没处理好，现在想想，如果当前位为“0”，那么dp[i] = dp[i - 2] 即可。
利用动态规划,dp[i]表示当前位置至往前的字符串共有多少种表示方式。

代码如下：

public int numDecodings(String s) {
    int len = s.length();
    int [] dp = new int[len + 1];
    dp[len] = 1 ; //
    //如果最后一个数字不等于0，就初始化为1
    if(s.charAt(len - 1) != '0')
        dp[len - 1] = 1;
    for(int i = len - 2 ; i >= 0 ; i--){
        if(s.charAt(i) == '0' )
            //当前数字为0，构成不了任何字母，跳过
            continue;
        int ans1 = dp[i + 1];
        //保存后一串字符串的解码个数
        int ans2 = 0;
        int ten = (s.charAt(i) - '0') * 10;
        int one = s.charAt(i + 1) - '0';
        if(ten + one <= 26)
            ans2 = dp[i + 2];
        dp[i] = ans1 + ans2;
    }
    return dp[0];
}

自底向上动态规划

这题的测试用例什么奇葩，给我整了那么多的边界条件，我人都傻了。
101 输出2
100 输出0
00 输出0
这题就是在疯狂测试边界条件

public int numDecodings(String s) {
    int len = s.length();
    int [] dp = new int[len];
    if(s.charAt(0) == '0'){
        dp[0] = 0;
        return 0;
    }
    else dp[0] = 1;
    for(int i = 1; i < len ; i++){
        if(s.charAt(i) == '0'){
            if((s.charAt(i - 1) == '2' || s.charAt(i - 1) == '1')) {
                if (i == 1)
                    dp[i] = 1;
                else dp[i] = dp[i - 2];
            }
            else if(s.charAt(i - 1) == '0')
                return 0;
            continue;
        }
        int ans1 = dp[i - 1];
        int ans2 = 0;
        int ten = (s.charAt(i - 1) - '0') * 10;
        int one = s.charAt(i) - '0';
        if( ten > 0 && ten + one <= 26 ) {
            if(i == 1)
                ans2 = 1;
            else ans2 = dp[i - 2];
        }
        dp[i] = ans1 + ans2;
    }
    return dp[len - 1];
}

动态规划优化

来源题解

只需要 2 空间个就够了，更新的时候，指针移动一下即可。

public int numDecodings(String s) {
    int len = s.length();
    int end = 1;
    int cur = 0; 
    if (s.charAt(len - 1) != '0') {
        cur = 1;
    }
    for (int i = len - 2; i >= 0; i--) {
        if (s.charAt(i) == '0') {
            end = cur;//end 前移
            cur = 0;
            continue;
        }
        int ans1 = cur;
        int ans2 = 0;
        int ten = (s.charAt(i) - '0') * 10;
        int one = s.charAt(i + 1) - '0';
        if (ten + one <= 26) {
            ans2 = end;
        }
        end = cur; //end 前移
        cur = ans1 + ans2;

    }
    return cur;
}