有一个消息包含A-Z通过以下规则编码 ‘A’ -> 1 ‘B’ -> 2 … ‘Z’ -> 26 现在给你一个加密过后的消息，问有几种解码的方式 样例 给你的消息为12，有两种方式解码 AB(12) 或者 L(12). 所以返回 2
解题思路：用dp的思想，每次纪录在当前位置可以组成的编码数目，考虑当前位置和前一位置组成数字的大小范围是否在（10，26），要注意的是0的特殊性。 一刷没有ac，不应该。
public class Solution { /** * @param s a string, encoded message * @return an integer, the number of ways decoding */ 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 ? 0 : 1; for (int i = 2; i <= s.length(); i++){ if (s.charAt(i-1) - '0' != 0){ nums[i] = nums[i-1]; } int tmp = Integer.valueOf(s.substring(i-2,i)); if (tmp >= 10 && tmp <= 26){ nums[i] += nums[i-2]; } } return nums[s.length()]; } }