Decode-Ways 解码方法

 1 public class Solution {
 2     /**
 3      * @param s: a string,  encoded message
 4      * @return: an integer, the number of ways decoding
 5      */
 6     public int numDecodings(String s) {
 7         char[] c = s.toCharArray();
 8         int n = c.length;
 9         
10         // 判空，单独一个空串是没有解压方式的，而后面dp[0] = 1是因为后面一定有数字
11         // 只要有1个数字和空串组合那也是1种方式，所以才会初始化为1，而空串本身后面
12         // 就已经没有任何数字能被解压回去了，因此return 0 是有一定道理的。
13         if (n == 0) {
14             return 0;
15         }
16 
17         // write your code here
18         // 1、最后一步：如果只有一个数字，我们直接判断该数字是否在1~9范围之间，有就返回1，反之返回0
19         // 如果长度 > 1的话，我们就可以判断最后一个数字是否在1~9范围之间，并且还需要查看其与前一个数字
20         // 组成起来能否解码为一个字母，即10~26范围
21         // 要值得注意的是，像01这种是不能作为整体转为字母的，
22         // 如果能组成就看前i - 2个字母能组成有多少种方式
23         // 如果不能组成则只需看前i - 1个字母组成能有多少种方式
24         
25         // n + 1，划分型动态规划结合序列型动态规划，因为0个数字也是能组成一种的，这样一来初始化就很方便
26         int[] dp = new int[n + 1];
27 
28         // 初始化
29         dp[0] = 1;
30 
31         // 转移方程，这里考虑的是从前1个字母到前n个字母
32         for (int i = 1; i <= n; i++) {
33             // 默认一开始为0，因为要取决于前面i - 1和i - 2的情况
34             dp[i] = 0;
35             // 看当前一个数字是否在1~9范围之内，这里的下标不要忘了 - 1
36             int num = c[i - 1] - ‘0‘;
37             if (num >= 1 && num <= 9) {
38                 dp[i] += dp[i - 1];
39             }
40             if (i - 2 >= 0) {
41                 // 至少两个字母
42                 // 下面就需要判断当前前i个数字的最后两个数字能否解压为一个字母
43                 int temp = (c[i - 2] - ‘0‘) * 10 + (c[i - 1] - ‘0‘);
44                 if (temp >= 10 && temp <= 26) {
45                     dp[i] += dp[i - 2];
46                 }
47             }
48         }
49 
50         // 最后返回的是前n个字母的解码方式个数
51         return dp[n];
52     }
53 }