Related: LeetCode 639 - Decode Ways II
Count Possible Decodings of a given Digit Sequence
LeetCode - Decode Ways | Darren's Blog
A message containing letters from A-Z is being encoded to numbers using the following mapping:
Count Possible Decodings of a given Digit Sequence
LeetCode - Decode Ways | Darren's Blog
A message containing letters from A-Z is being encoded to numbers using the following mapping:
'A' -> 1
'B' -> 2
...
'Z' -> 26
Given an encoded message containing digits, determine the total number of ways to decode it.Input: digits[] = "1234" Output: 3 // The possible decodings are "ABCD", "LCD", "AWD"
We initialize the total count of decodings as 0. We recur for two subproblems.
1) If the last digit is non-zero, recur for remaining (n-1) digits and add the result to total count.
2) If the last two digits form a valid character (or smaller than 27), recur for remaining (n-2) digits and add the result to total count.
Transformation function as:
Count[i] = Count[i-1] if S[i-1] is a valid char
or = Count[i-1]+ Count[i-2] if S[i-1] and S[i-2] together is still a valid char.
X. DP
1.为什什么要⽤用DP？（因为是⼀一个⼀一个字符decode的，有递推的关系，⽽而
且明显有最优⼦子结构）
2. 可以⽤用递归吗？（递归可以求出解，但是是指数级复杂度的，然⽽而如果
⽤用记忆化搜索的话可以降到和DP⼀一样的复杂度）
3. 如果出现连续两个零会怎样？（答案肯定为零。然后加了了⼀行代码，遇
到连续两个零直接返回）
https://github.com/mintycc/OnlineJudge-Solutions/blob/master/Leetcode/091_Decode_Ways.java
https://leetcode.com/discuss/83547/java-clean-dp-solution-with-explanation
https://discuss.leetcode.com/topic/20456/dp-with-easy-understand-java-solution/2
https://leetcode.com/discuss/8527/dp-solution-java-for-reference
https://discuss.leetcode.com/topic/2562/dp-solution-java-for-reference
http://shanjiaxin.blogspot.com/2014/04/decode-ways-leetcode.html
http://www.jiuzhang.com/solutions/decode-ways/
public int numDecodings(String s) {
if (s==null||s.length()==0){
return 0;
}
// declare ways array with two extra space, because ways[i] also affect by ways[i+2]
int[] ways=new int[s.length()+2];
Arrays.fill(ways, 1);
int i=s.length()-1;
ways[i]=s.charAt(i)=='0'?0:1;
for (i=i-1; i>=0; i--){
if (s.charAt(i)=='0'){
// if current digit is '0', so no mater what right is, current ways should be 0;
ways[i]=0;
}
else{
// if current digit is not '0', current ways should be ways[i+1]
// because, for example s="12", i=0, ways[1]=1, then because current digit is not zero, so for
// each situation of when i=1, the current i=0 should be a valid way,
ways[i]=ways[i+1];
// check is current digit with right 1 digit can be a valid situation,so in this situation only s.charAt(i)=='1'||
// s.charAt(i)=='2' and s.charAt(i+1)<='6' can be valid situation, the ways[i] should + ways[i+2];
if (i+2<ways.length && s.charAt(i)=='1'||s.charAt(i)=='2' &&s.charAt(i+1)<='6'){
ways[i]+=ways[i+2];
}
}
}
return ways[0];
}
http://bangbingsyb.blogspot.com/2014/11/leetcode-decode-ways.html
Time Complexity of the above solution is O(n) and it requires O(n) auxiliary space. We can reduce auxiliary space to O(1) by using space optimized version discussed in the Fibonacci Number Post.
http://n00tc0d3r.blogspot.com/2013/02/the-number-of-ways-to-decode-message.html
https://discuss.leetcode.com/topic/45327/java-2ms-dp-solution-with-detailed-explanation-and-inline-comments
X. DP -O(1) space:
https://discuss.leetcode.com/topic/39698/share-my-2ms-java-solution-with-o-1-spqce
https://github.com/tingyu/Leetcode/blob/master/Decode%20Ways/DecodeWays.java
X. Memoization
http://siyang2leetcode.blogspot.com/2015/03/decode-ways.html
X. Brute force(DFS), time complexity = O(2^n)
https://longwayjade.wordpress.com/2015/04/26/leetcode-recursion-dp-decode-ways/
http://siyang2leetcode.blogspot.com/2015/03/decode-ways.html
1) If the last digit is non-zero, recur for remaining (n-1) digits and add the result to total count.
2) If the last two digits form a valid character (or smaller than 27), recur for remaining (n-2) digits and add the result to total count.
http://zhaonanleetcode.blogspot.com/2014/06/leetcode-decode-ways.html
public int numDecodings(String s) {
// Input validation.
if (s == null || s.length() == 0) return 0;
if (s.length() == 1) return 1;
counter = 0;
int len = s.length();
int start = 0;
helper(s, len, start);
return counter;
}
public void helper(String s, int len, int start) {
// Base case.
if (start >= len) {
counter ++;
return;
}
// Try one letter.
helper(s, len, start + 1);
// Try two letters.
if (start + 1 < len) {
char curr = s.charAt(start);
char next = s.charAt(start + 1);
int number = ((int)curr - (int)'0')* 10 + ((int)next - (int)'0');
if (number <= 26) {
helper(s, len, start + 2);
}
}
}
}
Read full article from LeetCode - Decode Ways | Darren's Blog
1) If the last digit is non-zero, recur for remaining (n-1) digits and add the result to total count.
2) If the last two digits form a valid character (or smaller than 27), recur for remaining (n-2) digits and add the result to total count.
Transformation function as:
Count[i] = Count[i-1] if S[i-1] is a valid char
or = Count[i-1]+ Count[i-2] if S[i-1] and S[i-2] together is still a valid char.
X. DP
1.为什什么要⽤用DP？（因为是⼀一个⼀一个字符decode的，有递推的关系，⽽而
且明显有最优⼦子结构）
2. 可以⽤用递归吗？（递归可以求出解，但是是指数级复杂度的，然⽽而如果
⽤用记忆化搜索的话可以降到和DP⼀一样的复杂度）
3. 如果出现连续两个零会怎样？（答案肯定为零。然后加了了⼀行代码，遇
到连续两个零直接返回）
https://github.com/mintycc/OnlineJudge-Solutions/blob/master/Leetcode/091_Decode_Ways.java
public int numDecodings(String s) {
int[] f = new int[s.length() + 1];
f[0] = 1;
int last = 0, last2 = 0;
for (int i = 0; i < s.length(); i ++) {
last = s.charAt(i) - '0';
last2 = last2 % 10 * 10 + last;
if (last > 0) f[i + 1] = f[i];
if (last2 > 9 && last2 < 27)
f[i + 1] += f[i - 1];
}
return f[s.length()];
}
https://discuss.leetcode.com/topic/20456/dp-with-easy-understand-java-solution/2
https://leetcode.com/discuss/8527/dp-solution-java-for-reference
I used a dp array of size n + 1 to save subproblem solutions.
public int numDecodings(String s) {
if(s == null || s.length() == 0) {
return 0;
}
int n = s.length();
int[] dp = new int[n+1];
dp[0] = 1;
dp[1] = s.charAt(0) != '0' ? 1 : 0;
for(int i = 2; i <= n; i++) {
int first = Integer.valueOf(s.substring(i-1, i));
int second = Integer.valueOf(s.substring(i-2, i));
if(first >= 1 && first <= 9) {
dp[i] += dp[i-1];
}
if(second >= 10 && second <= 26) {
dp[i] += dp[i-2];
}
}
return dp[n];
}dp[0] means an empty string will have one way to decode, dp[1] means the way to decode a string of size 1. I then check one digit and two digit combination and save the results along the way. In the end, dp[n] will be the end result.https://discuss.leetcode.com/topic/2562/dp-solution-java-for-reference
http://shanjiaxin.blogspot.com/2014/04/decode-ways-leetcode.html
public int numDecodings(String s) {
if (s == null || s.length() == 0)
return 0;
int n = s.length();
// table[i]: the number of decodings for s[i...]
int[] table = new int[n+1];
// table[n]: upon reaching the end, earlier digit(s) is a way of decoding itself
// It is used to handle the cases such as s="15"
table[n] = 1;
// Consider the last digit individually
char last = s.charAt(n-1);
if (last >= '1' && last <= '9')
table[n-1] = 1;
// Calculate table[i] according to s[i], table[i+1], and table[i+2]
for (int i = n-2; i >= 0; i--) {
char c = s.charAt(i);
if (c < '1' || c > '9') // s[i...] starts with invalid digit
table[i] = 0;
else if (c > '2' || c == '2' && s.charAt(i+1) > '6') // s[i,i+1] must be decoded together
table[i] = table[i+1];
else // Decoded as s[i], s[i+1...], or s[i,i+1], s[i+2...]
table[i] = table[i+1] + table[i+2];
}
// Return the number of decodings for s
return table[0];
}
http://www.jiuzhang.com/solutions/decode-ways/
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' ? 1 : 0; for (int i = 2; i <= s.length(); i++) { if (s.charAt(i - 1) != '0') { nums[i] = nums[i - 1]; } int twoDigits = (s.charAt(i - 2) - '0') * 10 + s.charAt(i - 1) - '0'; if (twoDigits >= 10 && twoDigits <= 26) { nums[i] += nums[i - 2]; } } return nums[s.length()]; }http://www.jyuan92.com/blog/leetcode-decode-ways/
public int numDecodings(String s) {
if (null == s || s.length() == 0 || s.charAt(0) == '0') {
return 0;
}
int[] dp = new int[s.length() + 1];
dp[0] = 1;
dp[1] = 1;
for (int i = 2; i <= s.length(); i++) {
if (isValid(s.substring(i - 1, i))) {
dp[i] += dp[i - 1];
}
if (isValid(s.substring(i - 2, i))) {
dp[i] += dp[i - 2];
}
}
return dp[s.length()];
}
private boolean isValid(String s) {
if (s.charAt(0) == '0') {
return false;
}
int num = Integer.parseInt(s);
return num > 0 && num < 27;
}
http://rleetcode.blogspot.com/2014/01/decode-ways-java.htmlpublic int numDecodings(String s) {
if (s==null||s.length()==0){
return 0;
}
// declare ways array with two extra space, because ways[i] also affect by ways[i+2]
int[] ways=new int[s.length()+2];
Arrays.fill(ways, 1);
int i=s.length()-1;
ways[i]=s.charAt(i)=='0'?0:1;
for (i=i-1; i>=0; i--){
if (s.charAt(i)=='0'){
// if current digit is '0', so no mater what right is, current ways should be 0;
ways[i]=0;
}
else{
// if current digit is not '0', current ways should be ways[i+1]
// because, for example s="12", i=0, ways[1]=1, then because current digit is not zero, so for
// each situation of when i=1, the current i=0 should be a valid way,
ways[i]=ways[i+1];
// check is current digit with right 1 digit can be a valid situation,so in this situation only s.charAt(i)=='1'||
// s.charAt(i)=='2' and s.charAt(i+1)<='6' can be valid situation, the ways[i] should + ways[i+2];
if (i+2<ways.length && s.charAt(i)=='1'||s.charAt(i)=='2' &&s.charAt(i+1)<='6'){
ways[i]+=ways[i+2];
}
}
}
return ways[0];
}
http://bangbingsyb.blogspot.com/2014/11/leetcode-decode-ways.html
int numDecodings(string s) { if(s.empty() || s[0]<'1' || s[0]>'9') return 0; vector<int> dp(s.size()+1,0); dp[0] = dp[1] = 1; for(int i=1; i<s.size(); i++) { if(!isdigit(s[i])) return 0; int v = (s[i-1]-'0')*10 + (s[i]-'0'); if(v<=26 && v>9) dp[i+1] += dp[i-1]; if(s[i]!='0') dp[i+1] += dp[i]; if(dp[i+1]==0) return 0; } return dp[s.size()]; }Also check Count Possible Decodings of a given Digit Sequence
Time Complexity of the above solution is O(n) and it requires O(n) auxiliary space. We can reduce auxiliary space to O(1) by using space optimized version discussed in the Fibonacci Number Post.
int countDecodingDP(char *digits, int n){ int count[n+1]; // A table to store results of subproblems count[0] = 1; count[1] = 1; for (int i = 2; i <= n; i++) { count[i] = 0; // If the last digit is not 0, then last digit must add to // the number of words if (digits[i-1] > '0') count[i] = count[i-1]; // If second last digit is smaller than 2 and last digit is // smaller than 7, then last two digits form a valid character if (digits[i-2] < '2' || (digits[i-2] == '2' && digits[i-1] < '7') ) count[i] += count[i-2]; } return count[n];}private boolean isTwoDigitCode(char a, char b) {
return (a=='1' || (a=='2' && b<='6'));
}
public int numDecodings(String s) {
int len = s.length();
int[] count = new int[len+1];
count[0] = (len <= 0) ? 0 : 1;
for (int i=1; i<=len; ++i) {
char c = s.charAt(i-1);
if ( c != '0' ) count[i] = count[i-1];
if ( i-1 > 0 && isTwoDigitCode(s.charAt(i-2), c) ) {
count[i] += count[i-2];
}
if ( count[i] == 0 ) return 0; // invalid
}
return count[len];
} https://discuss.leetcode.com/topic/45327/java-2ms-dp-solution-with-detailed-explanation-and-inline-comments
X. DP -O(1) space:
https://discuss.leetcode.com/topic/39698/share-my-2ms-java-solution-with-o-1-spqce
public int numDecodings(String s) {
if(s == null || s.length() == 0 || s.charAt(0) == '0') return 0;
int curWays = 1;
int preWays = 1;
int length = s.length();
for(int i = 1; i < length; i++){
int newCurWays = curWays;
if(s.charAt(i) == '0'){
if(s.charAt(i - 1) != '1' && s.charAt(i - 1) != '2') return 0;
else newCurWays = preWays;
}else if(s.charAt(i - 1) == '1' || (s.charAt(i - 1) == '2' && s.charAt(i) < '7')){
newCurWays += preWays;
}
preWays = curWays;
curWays = newCurWays;
}
return curWays;
}int numDecodings(string s) {
if (!s.size() || s.front() == '0') return 0;
// r2: decode ways of s[i-2] , r1: decode ways of s[i-1]
int r1 = 1, r2 = 1;
for (int i = 1; i < s.size(); i++) {
// zero voids ways of the last because zero cannot be used separately
if (s[i] == '0') r1 = 0;
// possible two-digit letter, so new r1 is sum of both while new r2 is the old r1
if (s[i - 1] == '1' || s[i - 1] == '2' && s[i] <= '6') {
r1 = r2 + r1;
r2 = r1 - r2;
}
// one-digit letter, no new way added
else {
r2 = r1;
}
}
return r1;
}2 public int numDecodings(String s) { 3 if (s==null || s.length()==0 || s.charAt(0)=='0') { 4 return 0; 5 } 6 int num1 = 1; 7 int num2 = 1; 8 int num3 = 1; 9 for (int i=1; i<s.length(); i++) { 10 if (s.charAt(i) == '0') { 11 if (s.charAt(i-1) == '1' || s.charAt(i-1) == '2') { 12 num3 = num1; 13 } 14 else return 0; 15 } 16 else { 17 if (s.charAt(i-1) == '0' || s.charAt(i-1) >= '3') { 18 num3 = num2; 19 } 20 else if (s.charAt(i-1)=='2' && (s.charAt(i) =='7'||s.charAt(i)=='8'||s.charAt(i)=='9')) { 21 num3 = num2; 22 } 23 else num3 = num2 + num1; 24 } 25 num1 = num2; 26 num2 = num3; 27 } 28 return num2; 29 }Also check http://gongxuns.blogspot.com/2012/12/leetcodedecode-ways.html
https://github.com/tingyu/Leetcode/blob/master/Decode%20Ways/DecodeWays.java
public int numDecodings(String s) {
int len = s.length();
int w1 = (len <= 0) ? 0 : 1, w2 = w1;
for (int i=1; i<=len; ++i) {
char c = s.charAt(i-1);
int temp = w2; // w1 = count[i-2], temp = w2 = count[i-1]
// update w2 to be count[i]
if ( c == '0' ) w2 = 0;
if ( i-1 > 0 && isTwoDigitCode(s.charAt(i-2), c) ) {
w2 += w1;
}
if ( w2 == 0 ) return 0; // invalid
// set w1 = temp = count[i-1], i.e. A[(i+1)-2]
w1 = temp;
}
return w2;
} X. Memoization
http://siyang2leetcode.blogspot.com/2015/03/decode-ways.html
public int numDecodings(String s) {
if(s == null || s.length() == 0) return 0;
Map<Integer, Integer> map = new HashMap<Integer, Integer>();
map. put(s.length(), 1);
return dfs(s, 0, map);
}
private int dfs(String s, int index, Map<Integer, Integer> map){
// check path memory
if(map.containsKey(index)) return map.get(index);
// recursion
int count = 0;
if(index+1 < s.length() &&(s.charAt(index) == '1' || s.charAt(index) == '2' && s.charAt(index+1) <= '6'))
count += dfs(s, index+2, map);
if(s.charAt(index) != 0)
count += dfs(s, index+1, map);
map.put(index, count);
return count;
}
You write
symbols.contains(str.substring(start, start + 1)) andsymbols.contains(str.substring(start, start + 2)) twice. But I love your approach. I think I can call it Path-Memorizing DFS. BTW, I tried simple DFS and get TLE. I think after path-memorizing, the time complexity is O(n). Great!
public int numDecodings(String s) {
if (s == null || s.length() == 0)
return 0;
Set<String> symbols = new HashSet<String>();
for (int i=1; i<=26; i++){
symbols.add(String.valueOf(i));
}
Map<Integer, Integer> map = new HashMap<Integer, Integer>();
return numDec(s, 0, map, symbols);
}
private int numDec(String str, int start, Map<Integer, Integer> map, Set<String> symbols) {
Integer count = map.get(start);
if (count != null){
return count;
}
if (start == str.length()){
return 1;
}
int numWays = 0;
if ((start + 1 <= str. length()) &&
symbols.contains(str.substring(start, start + 1)) )
numWays += numDec(str, start + 1, map, symbols);
if ((start + 2 <= str. length()) &&
symbols.contains(str.substring(start, start + 2)) )
numWays += numDec(str, start + 2, map, symbols);
map.put(start, numWays);
return numWays;
}
https://longwayjade.wordpress.com/2015/04/26/leetcode-recursion-dp-decode-ways/
public int numDecodings(String s) { int len = s.length(); if (len == 0) return 0; if (len == 1 ){ if (isValid(s.substring(0,1))) return 1; else return 0; } int res = 0; // at least have two elements here. if (isValid(s.substring(len-1))) res += numDecodings(s.substring(0,len-1)); if (isValid(s.substring(len-2))) res += numDecodings(s.substring(0,len-2)); return res; } public boolean isValid (String s){ if (s.length() == 0 ) return false; int i = Integer.parseInt(s); if ( i >= 1 && i <= 26 ) return true; else return false; }http://siyang2leetcode.blogspot.com/2015/03/decode-ways.html
public int numDecodings(String s) {
return dfs(s, 0);
}
private int dfs(String s, int index){
// base case
if(index >= s.length()) return 1;
// recursion
int count = 0;
if(index+1 < s.length() &&(s.charAt(index) == '1' || s.charAt(index) == '2' && s.charAt(index+1) <= '6'))
count += dfs(s, index+2);
if(s.charAt(index) != '0')
count += dfs(s, index+1);
return count;
} 1) If the last digit is non-zero, recur for remaining (n-1) digits and add the result to total count.
2) If the last two digits form a valid character (or smaller than 27), recur for remaining (n-2) digits and add the result to total count.
int countDecoding(char *digits, int n){ // base cases if (n == 0 || n == 1) return 1; int count = 0; // Initialize count // If the last digit is not 0, then last digit must add to // the number of words if (digits[n-1] > '0') count = countDecoding(digits, n-1); // If the last two digits form a number smaller than or equal to 26, // then consider last two digits and recur if (digits[n-2] < '2' || (digits[n-2] == '2' && digits[n-1] < '7') ) count += countDecoding(digits, n-2); return count;}
public class Solution {
int counter;public int numDecodings(String s) {
// Input validation.
if (s == null || s.length() == 0) return 0;
if (s.length() == 1) return 1;
counter = 0;
int len = s.length();
int start = 0;
helper(s, len, start);
return counter;
}
public void helper(String s, int len, int start) {
// Base case.
if (start >= len) {
counter ++;
return;
}
// Try one letter.
helper(s, len, start + 1);
// Try two letters.
if (start + 1 < len) {
char curr = s.charAt(start);
char next = s.charAt(start + 1);
int number = ((int)curr - (int)'0')* 10 + ((int)next - (int)'0');
if (number <= 26) {
helper(s, len, start + 2);
}
}
}
}
Read full article from LeetCode - Decode Ways | Darren's Blog
