1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| public class DecodeWays {
public int numDecodings(String s) {
if (s.length() == 0) {
return 0;
}
int[] dp = new int[s.length()+1];
dp[s.length()] = 1;
dp[s.length()-1] = s.charAt(s.length()-1) == 0? 0: 1;
for (int i=s.length()-2; i>=0; i--) {
if (s.charAt(i) == '0') continue;
if (Integer.parseInt(s.substring(i, i+2))<=26)
dp[i] = dp[i+1] + dp[i+2];
else
dp[i] = dp[i+1];
}
return dp[0];
}
}
|
