LeetCode - Decode Ways

題目：

A message containing letters from A-Z is being encoded to numbers using the following mapping:

'A' -> 1
'B' -> 2
...
'Z' -> 26

Given an encoded message containing digits, determine the total number of ways to decode it.

For example,
Given encoded message "12", it could be decoded as "AB" (1 2) or "L" (12).

The number of ways decoding "12" is 2.

思路：

分情況討論

1. 當前字元為0

    1.1 前一個字元為0,3-9.

    1.2 前一個字元為1,2

2. 當前字元非0

    2.1 前一個字元為0,3-9

    2.2 前一個字元為2，當前字元為7-9

    2.3 餘下情況

package dp;

public class DecodeWays {

    public int numDecodings(String s) {
        int n;
        if (s == null || (n = s.length()) == 0) return 0;
        int[] dp = new int[n + 1];
        dp[0] = 1;
        if (s.charAt(0) == '0') return 0;
        dp[1] = 1;
        for (int i = 2; i <= n; ++i) {
            if (s.charAt(i - 1) == '0') {
                if (s.charAt(i - 2) != '1' && s.charAt(i - 2) != '2') return 0;
                dp[i] = dp[i - 2];
            } else if (s.charAt(i - 2) == '0' || s.charAt(i - 2) > '2' || 
                    (s.charAt(i - 2) == '2' && s.charAt(i - 1) > '6')) {
                dp[i] = dp[i - 1];
            } else {
                dp[i] = dp[i - 1] + dp[i - 2];
            }
        }
        return dp[n];
    }
    
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        DecodeWays d = new DecodeWays();
        System.out.println(d.numDecodings("10") == 1);
        System.out.println(d.numDecodings("101") == 1);
        System.out.println(d.numDecodings("1001") == 0);
        System.out.println(d.numDecodings("10012") == 0);
        System.out.println(d.numDecodings("0012") == 0);
        System.out.println(d.numDecodings("12") == 2);
        System.out.println(d.numDecodings("128") == 2);
        System.out.println(d.numDecodings("27") == 1);
        System.out.println(d.numDecodings("99") == 1);
    }

}

 更簡化一下：

package dp;

public class DecodeWays {

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

        for (int i = 2; i <= n; ++i) {
            int c1 = 0;
            if (s.charAt(i - 1) != '0')
                c1 = dp[i - 1];
            int c2 = 0;
            if (s.charAt(i - 2) == '1' || (s.charAt(i - 2) == '2' && s.charAt(i - 1) < '7'))
                c2 = dp[i - 2];
            dp[i] = c1 + c2;
        }
        
        return dp[n];
    }
    
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        DecodeWays d = new DecodeWays();
        System.out.println(d.numDecodings("10") == 1);
        System.out.println(d.numDecodings("101") == 1);
        System.out.println(d.numDecodings("1001") == 0);
        System.out.println(d.numDecodings("10012") == 0);
        System.out.println(d.numDecodings("0012") == 0);
        System.out.println(d.numDecodings("12") == 2);
        System.out.println(d.numDecodings("128") == 2);
        System.out.println(d.numDecodings("27") == 1);
        System.out.println(d.numDecodings("99") == 1);
    }

}