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.
Given encoded message 12, it could be decoded as AB (1 2) or L(12).
The number of ways decoding 12 is 2.
思路：
动态规划，用一个int数组表示0~i个字符组成的字符串解码方法总数
状态转移分3种情况：
1. 第i个字符有效，第i - 1个和第i个字符组成的字符串也有效，count[i] = count[i - 1] + count[i - 2];
2. 第i个字符有效，第i - 1个和第i个字符组成的字符串无效，count[i] = count[i - 1]
3. 第i个字符无效，第i - 1个和第i个字符组成的字符串有效，count[i] = count[i - 2];
4. 都无效，返回0
public class Solution { /** * @param s a string, encoded message * @return an integer, the number of ways decoding */ public int numDecodings(String s) { // Write your code here if(s == null || s.length() == 0) return 0; if(s.length() == 1){ if(isValid(s)) return 1; else return 0; } int length = s.length(); int[] count = new int[length]; if(isValid(s.substring(0, 1))) count[0] = 1; else return 0; if(isValid(s.substring(0, 2)) && isValid(s.substring(1, 2))) count[1] = 2; else if(!isValid(s.substring(0, 2)) && isValid(s.substring(1, 2))) count[1] = 1; else if(isValid(s.substring(0, 2)) && !isValid(s.substring(1, 2))) count[1] = 1; else return 0; for(int i = 2; i < length; i++){ boolean flag1 = isValid(s.substring(i - 1, i + 1)); boolean flag2 = isValid(s.substring(i, i + 1)); if(flag1 && flag2) count[i] = count[i - 1] + count[i - 2]; else if(!flag1 && flag2) count[i] = count[i - 1]; else if(flag1 && !flag2) count[i] = count[i - 2]; else return 0; } return count[length - 1]; } public boolean isValid(String s){ if(s.charAt(0) == ‘0‘) return false; int num = Integer.parseInt(s); if(num <= 26) return true; else return false; } }
原文：http://www.cnblogs.com/goblinengineer/p/5291593.html