LintCode习题系列之解码方法

前言

这是笔者在LintCode社区刷题的经历，希望思考的过程对读者有所帮助

解码方法

题目描述：
有一个消息包含A-Z通过以下规则编码
‘A’ -> 1 直到 ‘Z’ -> 26
现在给你一个加密过后的消息，问有几种解码的方式

实例:
12 : 1|2 代表AB，12代表L，共两种情况

思路：
首先排除特殊情况：
①若输入的String为“”，则结果为0
②若输入的String位数为1，则结果为1

然后是思路，也就是动态规划的自底向上实现：
①我们假设有数字串1232435，已知当前结果为X，则在后续插入5，变成12324355，结果会如何？
我们有且只有两种分法： 1232435|5 123243|55
前者结果也为X，而后者结果为0，因为55显然无法对应一个英文字母（在这里我们不关心1232435的X中方法具体是什么，因为满足无后效性，也就是可以动态规划解决），此时结果为X+0 = X.
②同样的，如果是12321，后续插入1，则分为两种情况：
12321|1 1232|11
也就是说，我们可以得出前四位的最佳解 + 前五位的最佳解 = 第六位最佳解！(仅当56位的数字合起来属于1-26之间)

实现中的漏洞：
实现中发现了一个格格不入的数字 0
当0出现时，只能搭配成10或者20，且（敲黑板）重要的是，10，20将整个数字隔开了！！
举个栗子12334510324201314，因为10和20的存在，必须分为
123345|10|324|20|1314, 也就是说，此时此刻，结果应该是123345的值*324的值*1314的值，获取值的方法参考之前的动态规划即可。

因此代码思路如下：
①判断s是否为“”，或者长度是否为1
②如果存在第一位是0，或者0之前不是1，2，那么无法分割，结果为0
③将整个数字按照10和20隔开，分别计算每一段的可能的分割数
④s的第一位必须为1或者2，其他数字比如说第一位为3，则3肯定和后续数字分开，因为3作十位必然超过30，无法转为字母，可以稍作处理。
⑤因为推当前位必须知道前两位，所以推下标为2的数字必须依靠0和1，0和1需要自行初始化。

代码：综上，代码如下

public static int numDecodings(String s) {
    if (s.length() == 0) {
        return 0;
    }

    char[] cs = s.toCharArray();
    if (cs[0] == '0') {
        return 0;
    }
    for (int j = 1; j < cs.length; j++) {
        if (cs[j] == '0' && cs[j - 1] != '1' && cs[j - 1] != '2') {
            return 0;
        }
    }

    int i = 0;
    for (; i < s.length(); i++) {
        String stemp = s.substring(i, i + 1);
        if ("1".equals(stemp) || "2".equals(stemp)) {
            break;
        }
    }
    s = s.substring(i).replace("10", " ").replace("20", " ");

    String[] ss = s.split(" ");
    int result = 1;
    for (String stemp : ss) {
        result *= calculate(stemp);
    }
    return result;
}

private static int calculate(String s) {
    if (s.length() <= 1) {
        return 1;
    }

    if (s.length() == 2) {
        int temp = Integer.valueOf(s);
        if (temp <= 26) {
            return 2;
        } else {
            return 1;
        }
    }

    int[] num = new int[s.length()];
    num[0] = 1;
    if (Integer.valueOf(s.substring(0, 2)) <= 26) {
        num[1] = 2;
    } else {
        num[1] = 1;
    }

    for (int j = 2; j < num.length; j++) {
        int temp = Integer.valueOf(s.substring(j - 1, j + 1));
        if (temp <= 26) {
            num[j] = num[j - 2] + num[j - 1];
        } else {
            num[j] = num[j - 1];
        }
    }

    return num[num.length - 1];
}

经测试，代码成功通过检验

结语

谢谢您的阅读，希望对您有所帮助