题解 | 把数字翻译成字符串

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 解码
     * @param nums string字符串 数字串
     * @return int整型
     */
    public int solve (String nums) {
        if (nums.contains("00")) {
            return 0;
        }
        char[] charArray = nums.toCharArray();
        if (charArray[0] == '0') {
            return 0;
        }
        int n = charArray.length;
        int result = 1;
        int lastlastInt = 100;

        int[] dp = new int[n];
        dp[0] = 1;
        for (int i = 1; i < n; i++) {
            int lastInt = Integer.parseInt(charArray[i - 1] + String.valueOf(charArray[i]));
            if (lastInt <= 26) {
                if (i >= 2) {
                    lastlastInt = Integer.parseInt(charArray[i - 2] + String.valueOf(
                                                       charArray[i - 1]));
                }
                if (lastlastInt <= 26) {
                    if (charArray[i - 1] != '0') {
                        result += dp[i - 2];
                    }
                } else {
                    if (charArray[i] != '0') {
                        result *= 2;
                    }
                }
            } else {
                if (charArray[i] == '0') {
                    return 0;
                }
            }
            dp[i] = result;
        }
        return result;
    }
}

以函数f(n)代表前n位的解个数。

我们以字符串142216为例进行拆解

f(1)=1;

只有两位数字14时，有2种,f(2)=2

1，4和14.

再加上一位2，由于2和最后一位4组成的数字42大于26.

所以，还是只有两组解,f(3)=2

1，4，2

14，2

后面再来一位2，结合后22是小于26的.

所以解的个数肯定会增加的。

增加多少需要看后两位结合的数字是否大于26，如果大于则只会增加前两位的个数。

否则就翻倍了。

这里最后两位的组合是42，大于26，所以直接翻倍了,因为可以直接写后面，又可以跟最后一个数字组合成一个新数。

f(4)=4;

解为

1，4，2，2（直接写后面）

14，2，2（直接写后面）

1，4，22（组合成新数）

14，22（组合成新数）

后面再来一个1，最后两个数字组合后是21小于26，所以解要增加，增加多少呢？

先把前面的解抄过来，后面再加上1

1，4，2，2，1

14，2，2，1

1，4，22，1

14，22，1

由于最后两位是可以组合的，所以可以是21结尾，那么增加的个数其实就是f(3)的解的个数。

把f(3)的答案抄下来，然后再后面加上21

1，4，2，21

14，2，21

所以f(5)=f(4)+f(3)=4+2=6.

通解就是当组合后的最后两位大于26时

f(n)=f(n-1);

组合后的最后两位小于26时，需要看倒数第三位和倒数第二位组合的数字是否大于26.

如果不大于，则

f(n)=f(n-1)+f(n-2);

如果大于

f(n) = 2f(n-1);

对0的特殊处理

要通过所有的用例，还需要做好对0的处理。因为0不能单独存在，必须依附前面的数字。

如果最后一位是0，是不能翻倍的。

倒数第二位为0，也不能加上f(n-2).

还有两种特殊情况，

（1）如果出现了00，那么一定是无解的。例如100

（2）0跟前面的数字结合后大于26，也是无解的。例如160。