My code:
public class Solution {
public int numDecodings(String s) {
if (s == null || s.length() == 0)
return 0;
if (s.charAt(0) < '1' || s.charAt(0) > '9')
return 0;
else if (s.length() == 1)
return 1;
int[] dp = new int[s.length() + 1];
if (s.charAt(0) >= '1' && s.charAt(0) <= '9')
dp[1] = 1;
else
dp[1] = 0;
dp[0] = 1;
for (int i = 2; i < dp.length; i++) {
if (s.charAt(i - 1) < '0' || s.charAt(i - 1) > '9')
return 0;
int v = Integer.parseInt(s.substring(i - 2, i));
if (v > 9 && v <= 26)
dp[i] += dp[i - 2];
if (s.charAt(i - 1) > '0' && s.charAt(i - 1) <= '9')
dp[i] += dp[i - 1];
else if (s.charAt(i - 1) == '0' && dp[i] == 0)
return 0;
}
return dp[dp.length - 1];
}
public static void main(String[] args) {
Solution test = new Solution();
System.out.println(test.numDecodings("10"));
}
}
My test result:
这道DP花了我接近两个小时，看了别人的代码，理解了好久才搞懂。
其实，DP的话，思路一定要清晰。比如这道题目。
求这个东西。
那么我设一个数组， dp[s.length()+1]
dp[i] 表示从s[0] - s[i - 1] 这一段区域，有多少种构造方法。
那么，有多少种呢？只有两种可能。
- (s[i - 2], s[i - 1])
- (s[i - 2]), (s[i - 1])
那么就直接点，考虑第一种因素。
即前面两位在 1-26之间就行了。
于是，dp[i] += dp[i - 2], 先把第一种情况加上去
这个很容易计算。
此时，不需要去考虑什么0不0的。
然后考虑第二种情况。
那么，因为DP，我可以保证s[i - 2] 是符合的。
于是只用判断s[i - 1]是否符合 1-9.
如果是， dp[i] += dp[i - 1]
然后还需要考虑一种情况， 如果 s[i - 1] == '0' 呢？
按道理，是无法进行下去了，应该直接返回0.
但是如果s[i - 2] 在 1-2范围内，就可以构成，10, 20，于是可以继续进行下去。
那么该怎么区分这种情况呢？难道还要再去判断下s[i - 2]？
不用了，如果s[i - 2] 在 1-2 范围内，就满足了第一种情况，那么dp[i] 就已经被赋值了，已经大于0了。
所以最后只用判断下dp[i]是否为0，是否被赋值过了，如果没有。代表s[i - 2]不在1-2范围内。那么这里就无法再继续decode，得直接返回0.
一开始这道题目我是拿递归做的，思路和permutation那个类型差不多，但是超时了。的确其中有许多重复的地方。
DP还是难啊。
贴一个博客。
http://bangbingsyb.blogspot.com/2014/11/leetcode-decode-ways.html
DP，思路一定要清晰，最好能像这里一样清楚地写下来。
**
总结： String, DP
**
Good luck, Richardo!
My code:
public class Solution {
public int numDecodings(String s) {
if (s == null || s.length() == 0) {
return 0;
}
int n = s.length();
int[] dp = new int[n];
dp[0] = (isDigit(s.charAt(0)) ? 1 : 0);
for (int i = 1; i < n; i++) {
int sum = 0;
char curr = s.charAt(i);
if (isDigit(curr)) {
if (i - 1 >= 0) {
sum += dp[i - 1];
}
else {
sum += 1;
}
}
String sub = s.substring(i - 1, i + 1);
if (isValid(sub)) {
if (i - 2 >= 0) {
sum += dp[i - 2];
}
else {
sum += 1;
}
}
dp[i] = sum;
}
return dp[n - 1];
}
private boolean isValid(String s) {
char c1 = s.charAt(0);
char c2 = s.charAt(1);
if (c1 == '1' && (c2 >= '0' && c2 <= '9')) {
return true;
}
else if (c1 == '2' && (c2 >= '0' && c2 <= '6')) {
return true;
}
else {
return false;
}
}
private boolean isDigit(char curr) {
if (curr >= '1' && curr <= '9') {
return true;
}
else {
return false;
}
}
}
这道题目我的思路还是很清晰的。
一开始我做的方向不对。
我又想到了用 divide and conquer, burst ballon + cache
这是一定可以work的。但存在一个问题，很难解决，或者需要很多的琐碎代码去解决。
如果输入是 '111'
那么，我的算法，会重复计算很多东西。而且很难察觉。只能通过hashset 来去重。这样的话，开销会变大。
于是我转而用 iteration DP.
dp[i] 表示， [0, i] number of decode ways
那么，
如果 s.charAt(i) 本身就是digit，dp[i] += dp[i - 1]
如果 s.substring(i - 1, i + 1) 是 "11 - 26"中的一员，那么
dp[i] += dp[i - 2]
然后加上一些corner case, 就可以完成这个问题了。
思路很直接。
Anyway, Good luck, Richardo! -- 08/26/2016
