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] 這一段區(qū)域大咱，有多少種構造方法。
那么舀患，有多少種呢徽级？只有兩種可能。
- (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，于是可以繼續(xù)進行下去志鹃。
那么該怎么區(qū)分這種情況呢夭问？難道還要再去判斷下s[i - 2]？
不用了曹铃，如果s[i - 2] 在 1-2 范圍內缰趋，就滿足了第一種情況，那么dp[i] 就已經被賦值了陕见，已經大于0了埠胖。
所以最后只用判斷下dp[i]是否為0，是否被賦值過了淳玩，如果沒有。代表s[i - 2]不在1-2范圍內非竿。那么這里就無法再繼續(xù)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
