解码方法 Decode Ways

[Shellbye]

被上一个题目（ #43 ）暴虐之后，我变得谦虚了不少，虽然我是从难到易的在做，但是这只是一个从通过率的角度来衡量的，而且不同的题目解题思路差异还挺大，真不能掉以轻心。

题目

一条包含字母 A-Z 的消息通过以下方式进行了编码： 'A' -> 1 'B' -> 2 ... 'Z' -> 26 给定一个只包含数字的非空字符串，请计算解码方法的总数。

示例 1:

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

示例 2:

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

思路01

这也是一个动态规划的题目，根据其特性，首先想到的就是把它的情况分成包含第一个字符和不包含第一个字符两类。这里的每一个字符还不是等价的，其中的1, 2, 0三个字符比较特殊，前两者和后面的部分或全部组合之后会有其他含义，而最后一个0则是不能和后面的字符组合，且自己单独也不能独立，所以这三个字符需要特殊考虑。

1. 如果当前字符是1，那么只要后面不是0，则解码方法就会多一种，因为有1独立、合并后面两种方法；
2. 如果当前字符是2，那么只要后面不是7, 8, 9, 0，则解码方法也会多一种，原因同上。
3. 不同的组合之间要用乘积组合，但是前提是他们之间彼此没有重叠，比如121这种情况，中间的2是只能够利用一次的，不能重复计算。

思路02

隔了几天之后，有突然根据一个评论里面说到的“爬楼梯”想到了另一个思路，就是每次分析到某一个字符时，都看一下这个字符是否把后面的字符分成了两类，具体的分类方式和上面还是一样的。比如字符串192756，当分析到1的时候，就可以发现1之后有两种走法，一种是把92756当做一个全新的去继续分析，另一种就是把2756当作一个全新的去分析，其中的9和1合并了。

思路03

上面的两个思路都是站在当前字符向后看，但是我在网上搜索了一些资料，发现大家都是站在当前字符向前看，想想也对，后面的都是不知道的，但是不能向后看了，前面因为已经处理过了，所以是知道的，因此应该向前看。具体怎么向前看呢？参考一下对1212的处理逻辑

1 第一种：1

12 第一种：1,2 DL 第二种：12 HT

121 第一种：1,2,1 DL 第二种：1,21 HT 第三种：12,1 DL

1212 第一种：1,2,1,2 DL 第二种：1,2,12 HT 第三种：1,21,2 DL 第四种：12,12 HT 第五种：12,1,2 DL

12121 第一种：1,2,1,2,1 DL 第二种：1,2,1,21 HT 第三种：1,2,12,1 DL 第四种：1,21,2,1 DL 第五种：1,21,21 HT 第六种：12,12,1 DL 第七种：12,1,2,1 DL 第八种：12,1,21 HT

通过以上的几种详细分析，我们可以发现处理新出现的字符，主要有两种方法： 1.新字符“独立”为一种解码方法（标记DL） 2.新字符尝试贴在原有解码方法中最后一个字符的后面，与之“合体”（标记HT）

经过以上的分析，当字符串是由1和2构成的时候，这种情况比较简单，我们能得出以下状态转移方程：

dp[i]=dp[i-1]+dp[i-2]

关于为什么是以上方程，我纳闷了好一阵，肯定不是因为这是斐波那契数列，因为有更深层次的原因，再次看了一遍上面的五个详细分析之后，我明白过来了。就拿12121中情况来说，为什么它是1212和121两种方式的和呢？因为12121有两种方式构成，一种是直接复制1212下来，然后在末尾加上新出现的字符1（“独立”DL）；另一种就是把新出现的字符1，与前一个字符“合体”(HT），那有几种“合体”的方式呢？理论上讲应该是1212中五种全部，因为他们都是2结尾的，但是真实情况不允许，为什么呢？因为1212中的五种，有三种“独立”和两种“合体”，而这三种“独立”，恰好来自121的三种方式。所以就刚好是 5+3，也就是我们上面的状态转移方程dp[i]=dp[i-1]+dp[i-2]。

特殊情况

因为我们上面分析的这个输入字符串1212太特殊，所以我们再来分析一个19210

1 第一种：1

19 第一种：1,9 DL 第二种：19 HT

192 第一种：1,9,2 DL 第二种：19,2 DL

1921 第一种：1,9,2,1 DL 第二种：1,9,21 HT 第三种：19,2,1 DL 第四种：19,21 HT

19210 第一种：1,9,2,10 HT 第二种：19,2,10 HT

通过上面的分析我们可以发现，上面提到的“独立”和“合体”这两种方法并不是总会发生，有些时候只能“独立”：

1. 前一个字符不是1或2
2. 即使前一个字符是2，当前字符为7,8,9
3. 前一个字符已经和前前一个字符“合体”过了

有些时候只能“合体”（当前字符为0），还有一些时候，比如上面的这个情况，解码方法不仅仅没有增加，还急剧减少了。。。

代码进化史🧬

因为自己算法方面比较差，所以很多题目苦思冥想之后依然没有思路时，我就会去网上看别人的解析，但是，我在看很多算法解析的时候，常常只是看到了完美执行的代码，却搞不懂是怎么来的，所以我自己写的时候，就会尽量避免直接丢一段代码的模式，针对这道题，我准备尝试一种把整个过程写下来的新方法。

1.最简单版本

针对上面 思路3 的情况，我们可以写出如下的V0版本

    public int numDecodingsV0(String s) {
        if (s == null || s.length() == 0 || s.charAt(0) == '0') return 0;

        int[] dp = new int[s.length()];
        dp[0] = 1;
        dp[1] = 2;

        for (int i = 2; i < s.length(); i++) {
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        return dp[s.length() - 1];
    }

以上代码针对完全由1和2构成的字符串是没问题的，这也是最简单的版本。它虽然简单，但是也麻雀虽小五脏俱全，代码主体有三大块，第一块是第一行，表示一些对异常输入的检查和快速返回；第二块是接下来三行，是一些初始化工作，类似递归证明的1和n-1；第三块是主体循环，几乎在所有的算法题中，这个主体循环都是核心，这里也是时间复杂度的决定性部分；最后就是返回答案了，这个没啥需要说的。

上面的代码之所以只能处理1和2构成的字符串，是因为它认为所有的新字符都可以进行“合体”（HT）和“独立”（DL），所以当其中出现其他字符时，就不行了。那么为了兼容其他字符，我们需要进行一些调整。

2.考虑其他字符

字符1和2和其他字符有什么不同之处呢？这个不同就在与能否随时随地的自由的“独立”和“合体”，比如字符8，它只有在前面是1的时候才能“合体”，如果前面不是1就不行了，那么怎么判断当前字符和前面的字符能不能“合体”呢？这个时候结合题目信息我们可以判断，当两个数字小于等于26时，就是可以的（0比较特殊，稍后重点讨论）。于是我们的代码就更新成了下面这样

    public int numDecodingsV1(String s) {
        if (s == null || s.length() == 0 || s.charAt(0) == '0') return 0;
        int[] dp = new int[s.length()];
        dp[0] = 1;
        if (Integer.parseInt(s.substring(0, 2)) <= 26) {
            dp[1] = 2;
        } else {
            dp[1] = 1;
        }

        for (int i = 2; i < s.length(); i++) {
            String a = s.substring(i - 1, i + 1);
            if (Integer.parseInt(a) <= 26) {
                // 独立+合体数目
                dp[i] = dp[i - 1] + dp[i - 2];
            } else {
                // 仅独立数目
                dp[i] = dp[i - 1];
            }
        }
        return dp[s.length() - 1];
    }

其中比较关键的新增内容就是Integer.parseInt(s.substring(0, 2)) <= 26这个判断，并根据其结果选择不同的路径，如果为真，则可以有“合体”和“独立”两种选择，与1,2类似，如果为假，则只能“独立”，不能“合体”。 截止目前，在不包含0的情况下，我们都可以轻易处理了，接下来就要重点考虑包含0的情况了。

3.把0也考虑进去

字符0的特殊之处我们在上面已经见识过了，它是不能“独立”只能“合体”的，而且有些时候它的“合体”还会导致解码方法的减少（比如110，从两种变成一种），还有时候它甚至会导致整个字符串无法解码，即算法返回0（比如9912302144）。总结起来，关于0有以下几种情况：

1. 0在开头，返回 0；
2. 0前面的字符不是1或者2，字符串非法，返回 0；
3. 0前面是1或者2，此时解码方法要缩减，缩减的部分为0前面的部分“合体”形成的，也就是0前面的字符再前面的字符所带来的数目（相见上面的分析）。
4. 在上面的比较中，直接选出两位数与26比较其实是有点粗粒度了，因为其中可能包含05这种情况，05虽然符合小于26但是它却不能作答自由的“独立”或者“合体”。能完全真正作答的，还需要满足大于10。 基于以上几点考虑，和一些特殊的测试用例（1, 20），我们的代码应该是如下的样子

    public int numDecodings(String s) {
        if (s == null || s.length() == 0 || s.charAt(0) == '0')
            return 0;
        if (s.length() == 1)
            return 1;
        int[] dp = new int[s.length()];
        dp[0] = 1;
        String a0 = s.substring(0, 2);
        if (Integer.parseInt(a0) <= 26 && Integer.parseInt(a0) > 10 && s.charAt(1) != '0') {
            dp[1] = 2;
        } else if (s.charAt(1) == '0' && !(s.charAt(0) == '1' || s.charAt(0) == '2')) {
            return 0;
        } else {
            dp[1] = 1;
        }

        for (int i = 2; i < s.length(); i++) {
            String a = s.substring(i - 1, i + 1);
            // 计算独立数
            if (s.charAt(i) != '0') {
                // 只要当前的字符不是 0 ，就表示通过独立可以实现继承前面的解码数
                dp[i] = dp[i - 1];
            }
            // 计算合体数
            if (Integer.parseInt(a) <= 26 && Integer.parseInt(a) >= 10) {
                // 有合体的可能性，加上潜在合体数，即前一个的前一个
                dp[i] += dp[i - 2];
            }
            // 0 前面不是 1 或者 2 就返回 0
            if (s.charAt(i) == '0' && !(s.charAt(i - 1) == '1' || s.charAt(i - 1) == '2'))
                return 0;
        }
        return dp[s.length() - 1];
    }

这是一个可以通过的版本，🎉🎉🎉，但是我可以看到，虽然中间的循环逻辑稍微清楚一点，但是第一部分的初始化做的实在是惨不忍睹，明显就是针对各种特殊测试用例打的补丁。

4.一点思考

因为我的初始化做的实在是太差了，所以查了一些其他人的做法，

    public int numDecodings(String s) {
        int n = s.length();
        if (n == 0) {
            return 0;
        }
        
        int[] dp = new int[n + 1];
        dp[0] = 1;
        dp[1] = (s.charAt(0) == '0') ? 0 : 1;
        
        for (int i = 2; i <= n; i++) {
            if (s.charAt(i - 1) != '0') {
                dp[i] = dp[i - 1];
            }
            int twoDigits = Integer.parseInt(s.substring(i - 2, i));
            if (twoDigits >= 10 && twoDigits <= 26) {
                dp[i] += dp[i - 2];
            }
        }
        
        return dp[s.length()];
    }

以上是别人提供的一个解法，这个解法的初始化方法是非常简洁明了的，而且循环内部也逻辑更简单，总之是各个方面都比我的原始方法要好。我对比了一下两个解法的差异，发现我们的差异的关键点在于赋给dp中每一个结点的意义是不一样的，在我的解法中，dp[i]表示输入字符分析到第i个结点（包含）时，可能的解码方法总数；而上面的这个更简洁的解法中，dp[i]表示的却不包含当前的第i个结点，比如同样的一组输入数据（12121），最后的dp数组分别如下：

[1, 2, 3, 5, 8]       // 我的
[1, 1, 2, 3, 5, 8]   // 别人的

通过上面的输出我们可以看到，在别人的解法中，它的第一位其实是没有严格的物理意义的，那么问题来了：为什么要加这么一个没有物理意义的点呢？（这个点貌似有一个算法领域的专有名字，我想不起来了）虽然这个点没有物理意义，但是它却有一个重要的作用，那就是可以把第二个元素纳入到循环中。什么意思呢，其实我们的初始化代码之所以混乱，就是因为我在循环之前不仅仅处理了第一个字符，而且也处理了第二个字符，所以才会有那么多的和循环里面逻辑差不多的代码。为什么会这样呢，因为这个循环是一个依赖两个元素的，如果只初始化一个元素，还不够进入循环的条件，如果初始化两个，就会显得比较乱（比如我的），这时，引入一个无物理意义的点就像引入了辅助线一样，就可以把这个问题解决了。

5.优化

经过上面的思考，最终优化如下

    public int numDecodings(String s) {
        if (s == null || s.length() == 0 || s.charAt(0) == '0')
            return 0;
        int[] dp = new int[s.length() + 1];
        dp[0] = 1;  // 辅助线
        dp[1] = 1;

        for (int i = 2; i < s.length() + 1; i++) {
            String a = s.substring(i - 2, i);
            // 计算独立(DL)数
            if (s.charAt(i - 1) != '0') {
                // 只要当前的字符不是 0 ，就表示通过独立可以实现继承前面的解码数
                dp[i] = dp[i - 1];
            }
            // 计算合体(HT)数
            if (Integer.parseInt(a) <= 26 && Integer.parseInt(a) >= 10) {
                // 有合体的可能性，加上潜在合体数，即前一个的前一个
                dp[i] += dp[i - 2];
            }
        }
        return dp[s.length()];
    }

其中唯一需要注意的就是下标的变化，其他逻辑基本上没啥变化。