一文解决解码问题

解码问题-线性dp

题目汇总

解码方法I

• 分析思路：

  动态规划，这道题跟跳台阶非常相似。由题意可知，数字[1-26]对应[a-z]。分析时可以考虑对于数字[1-9]，只能是一个数字对应一个字母[a-j];但是对于数字[11-26],可能对应两个字母，也可能对应一个字母。例如：12可以对应[ab]和l。因此要分别考虑这两种情况。对于具体做法，考虑使用动态规划。
  

• 状态表示

f[i]表示表示前 i个数字共有多少种解码方式
属性为方案数

• 状态计算

划分以最后一个解码的字母需要一个还是两个数字来分类。如果需要一个数字，那么满足第i个数字[1-9]即可，此时f[i]就由f[i - 1]转移得到；如果需要两个数字，需要满足这两个数字组成的新数字位于[10-26]，此时f[i]就由f[i - 2]转移得到。具体细节见代码:

• 代码

class Solution {
    public int numDecodings(String s) {
        int n = s.length();
        s = ' ' + s;
        // f[i]表示s中的前i个字符可以正确解码的方案数
        int[] f = new int[n + 1];
        f[0] = 1;
        for(int i = 1; i <= n; i++){
            // 最后一位数字代表一个字母
            if(s.charAt(i) >= '1' && s.charAt(i) <= '9') f[i] += f[i - 1];
            // 最后两个数字对应一个字母
            if(i > 1) {
                int t = (s.charAt(i - 1) - '0') * 10 + s.charAt(i) - '0';
                if(t >= 10 && t <= 26) f[i] += f[i - 2];
            }
        }
        return f[n];
    }
}

解码方法II

• 分析思路

本题属于上题的进阶，添加了*这个，对于状态转移方程有了很多细节的考验。如果还是按照上题思路，会多很多的细节判断，尤其是在双字符解码时。

• 代码

class Solution {
    public int numDecodings(String s) {
        int n = s.length();
        s = ' ' + s;
        int MOD = (int) (1e9 + 7);

        long[] f = new long[n + 1];
        f[0] = 1;

        for (int i = 1; i <= n; i++) {
            // j枚举的是可解码的最后一个字母对应的数字(1-26) 对应a-Z
            for (int j = 1; j <= 26; j++) {
                char a = s.charAt(i); //a表示当前位数字

                // 单字符解码
                if (j <= 9) {
                    if (a == '*' || a == (char)(j + '0')) {
                        f[i] = (f[i] + f[i - 1]) % MOD;
                    }
                }
                // 双字符解码
                else { 
                    if (i >= 2) {
                    char b = s.charAt(i - 1); // 取当前位的前一位数字
                    int y = j / 10, x = j % 10;// 求出来如果是双字符解码，要解码的数字是多少 y是十位 x是个位
                    if ((b == (char)(y + '0') || (b == '*' && y != 0)) && (a == (char)(x + '0') || (a == '*' && x != 0))) {
                        f[i] = (f[i] + f[i - 2]) % MOD;
                    }
                }
                }
            }
        }

        return (int) f[n];
    }
}

另外，在代码中为了防止处理边界，我都是将s前面添加一个空格，这样可以使得枚举的i是[1 - n]的，减少边界条件的处理，还要注意本题中的MOD运算。