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.
这道题有点像https://oj.leetcode.com/problems/climbing-stairs/爬梯子那道题，我在那道题的基础上用DP的思路，修修改改。写的略挫，一会儿去看看别人怎么A的
1 public class Solution { 2 public int numDecodings(String s) { 3 if(0 == s.length() || s.charAt(0) == ‘0‘) 4 return 0; 5 int ways[] = new int[s.length() + 1]; 6 for(int i = 0; i <= s.length(); i++){ 7 if(i == 1 || i == 0){ 8 ways[i] = 1; 9 } 10 else{ 11 if(i < s.length() && s.charAt(i) == ‘0‘) 12 { 13 ways[i] = ways[i - 1]; 14 continue; 15 } 16 String subStr = s.substring(i - 2, i); 17 int num = Integer.valueOf(subStr); 18 if(num == 0) 19 return 0; 20 if(num > 26 && num % 10 == 0) 21 return 0; 22 else if(num <= 26 && s.charAt(i - 1) != ‘0‘ && s.charAt(i - 2) != ‘0‘) 23 ways[i] = ways[i - 1] + ways[i - 2]; 24 else 25 ways[i] = ways[i - 1]; 26 }//else 27 }//for 28 29 return ways[s.length()]; 30 } 31 }
原文：http://www.cnblogs.com/luckygxf/p/4209129.html