/**
* Source : https://oj.leetcode.com/problems/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.
*/
public class DecodeWays {
/**
* 找出有多少种解码方式
*
* 使用递归，但是复杂度较高，可以考虑使用DP
*
* 当XY > 26的时候 dp[i+1] = dp[i]
* XY <= 26 的时候 dp[i+1] = dp[i] + dp[i-1]
*
*
* 临界条件：
* X = 0,dp[i+1] = dp[i]
* Y = 0,dp[i+1] = dp[i-1]
*
* @param digits
*/
public int findWays (String digits) {
if (digits == null || digits.length() == 0 || digits.charAt(0) < '1' || digits.charAt(0) > '9') {
return 0;
}
int[] dp = new int[digits.length() + 1];
dp[0] = dp[1] = 1;
for (int i = 1; i < digits.length(); i++) {
if (digits.charAt(i) > '9' || digits.charAt(i) < '1') {
return 0;
}
int x = digits.charAt(i-1) - '0';
int y = digits.charAt(i) - '0';
int xy = x * 10 + y;
if (xy > 9 && xy <= 26) {
dp[i+1] = dp[i] + dp[i-1];
} else if (y != 0) {
dp[i+1] = dp[i];
}
if (dp[i+1] == 0) {
return 0;
}
}
return dp[dp.length-1];
}
public static void main(String[] args) {
DecodeWays decodeWays = new DecodeWays();
System.out.println(decodeWays.findWays(""));
System.out.println(decodeWays.findWays("1"));
System.out.println(decodeWays.findWays("12"));
System.out.println(decodeWays.findWays("32"));
System.out.println(decodeWays.findWays("10"));
System.out.println(decodeWays.findWays("00"));
System.out.println(decodeWays.findWays("09"));
}
}