Problem 91: Decode Ways

https://leetcode.com/problems/decode-ways/

思路

• 和 word ladder 类似的一个 dp 题目

• 单个的数字只要不是 0 就对应一种方法；两位数的时候，考虑首位数字是否为 0

public class Solution {
    public int numDecodings(String s) {
        if (s == null || s.length() == 0) {
            return 0;
        }

        int[] nums = new int[s.length() + 1];
        nums[0] = 1;
        nums[1] = s.charAt(0) == '0' ? 0 : 1;
        for (int i = 2; i <= s.length(); i++) {
            if (s.charAt(i - 1) != '0') {
                nums[i] = nums[i - 1];
            }

            // 得到两位数的方法
            int twoDigits = (s.charAt(i - 2) - '0') * 10 + (s.charAt(i - 1) - '0');
            if (twoDigits >= 10 && twoDigits <= 26) {
                nums[i] += nums[i - 2];
            }
        }

        return nums[s.length()];
    }
}

• 优化空间

public class Solution {
    public int numDecodings(String s) {
        if (s == null || s.length() == 0) {
            return 0;
        }

        int prev = 27, digit = 0, single = 1, twoDigit = 1, rst = 0;
        for (int i = s.length() - 1; i >= 0; i--) {
            digit = s.charAt(i) - '0';
            if (digit == 0) {
                rst = 0;
            } else {
                rst = single + (digit * 10 + prev < 27 ? twoDigit : 0);
            }

            twoDigit = single;
            single = rst;
            prev = digit;
        }

        return rst;
    }
}

易错点

1. String s 和数组 nums 的 index 正好错一位

   比如 s.charAt(0) 对应的其实是 nums[1]

   if (s.charAt(i - 1) != '0') {
         nums[i] = nums[i - 1];
   }

2. 循环的 upper bound

   for (int i = 2; i <= s.length(); i++)

   之前写的是

   for (int i = 2; i <= nums.length; i++)

   就这么一个小细节，就会导致结果的越界。

   非常容易出错，第二次写的时候，又在这里错了！

3. 注意 charAt() 方法

   nums[1] = s.charAt(0) == '0' ? 0 : 1;

   写成了

   nums[1] = s.charAt(0) == 0 ? 0 : 1;

   少了引号，但是 compiler 是不会报错的。