Related: LeetCode 91 - Decode Ways
https://leetcode.com/problems/decode-ways-ii
https://leetcode.com/articles/decode-ways-ii/
http://www.cnblogs.com/grandyang/p/7279152.html
X. DP
https://discuss.leetcode.com/topic/95251/java-dp-o-n-time-and-o-1-space
https://discuss.leetcode.com/topic/95277/c-dp-o-n-time-o-1-space
https://leetcode.com/problems/decode-ways-ii
A message containing letters from
A-Z is being encoded to numbers using the following mapping way:'A' -> 1 'B' -> 2 ... 'Z' -> 26
Beyond that, now the encoded string can also contain the character '*', which can be treated as one of the numbers from 1 to 9.
Given the encoded message containing digits and the character '*', return the total number of ways to decode it.
Also, since the answer may be very large, you should return the output mod 109 + 7.
Example 1:
Input: "*" Output: 9 Explanation: The encoded message can be decoded to the string: "A", "B", "C", "D", "E", "F", "G", "H", "I".
Example 2:
Input: "1*" Output: 9 + 9 = 18
Note:
- The length of the input string will fit in range [1, 105].
- The input string will only contain the character '*' and digits '0' - '9'.
https://leetcode.com/articles/decode-ways-ii/
http://www.cnblogs.com/grandyang/p/7279152.html
这道解码的题是之前那道Decode Ways的拓展，难度提高了不少，引入了星号，可以代表1到9之间的任意数字，是不是有点外卡匹配的感觉。有了星号以后，整个题就变得异常的复杂，所以结果才让我们对一个很大的数求余，避免溢出。这道题的难点就是要分情况种类太多，一定要全部理通顺才行。我们还是用DP来做，建立一个一维dp数组，其中dp[i]表示前i个字符的解码方法等个数，长度为字符串的长度加1。将dp[0]初始化为1，然后我们判断，如果字符串第一个字符是0，那么直接返回0，如果是*，则dp[1]初始化为9，否则初始化为1。下面就来计算一般情况下的dp[i]了，我们从i=2开始遍历，由于要分的情况种类太多，我们先选一个大分支，就是当前遍历到的字符s[i-1]，只有三种情况，要么是0，要么是1到9的数字，要么是星号。我们一个一个来分析：
首先来看s[i-1]为0的情况，这种情况相对来说比较简单，因为0不能单独拆开，只能跟前面的数字一起，而且前面的数字只能是1或2，其他的直接返回0即可。那么当前面的数字是1或2的时候，dp[i]的种类数就跟dp[i-2]相等，可以参见之前那道Decode Ways的讲解，因为后两数无法单独拆分开，就无法产生新的解码方法，所以只保持住原来的拆分数量就不错了；如果前面的数是星号的时候，那么前面的数可以为1或者2，这样就相等于两倍的dp[i-2]；如果前面的数也为0，直接返回0即可。
再来看s[i-1]为1到9之间的数字的情况，首先搞清楚当前数字是可以单独拆分出来的，那么dp[i]至少是等于dp[i-1]的，不会拖后腿，还要看其能不能和前面的数字组成两位数进一步增加解码方法。那么就要分情况讨论前面一个数字的种类，如果当前数字可以跟前面的数字组成一个小于等于26的两位数的话，dp[i]还需要加上dp[i-2]；如果前面的数字为星号的话，那么要看当前的数字是否小于等于6，如果是小于等于6，那么前面的数字就可以是1或者2了，此时dp[i]需要加上两倍的dp[i-2]，如果大于6，那么前面的数字只能是1，所以dp[i]只能加上dp[i-2]。
最后来看s[i-1]为星号的情况，如果当前数字为星号，那么就创造9种可以单独拆分的方法，所以那么dp[i]至少是等于9倍的dp[i-1]，还要看其能不能和前面的数字组成两位数进一步增加解码方法。那么就要分情况讨论前面一个数字的种类，如果前面的数字是1，那么当前的9种情况都可以跟前面的数字组成两位数，所以dp[i]需要加上9倍的dp[i-2]；如果前面的数字是2，那么只有小于等于6的6种情况都可以跟前面的数字组成两位数，所以dp[i]需要加上6倍的dp[i-2]；如果前面的数字是星号，那么就是上面两种情况的总和，dp[i]需要加上15倍的dp[i-2]。
每次算完dp[i]别忘了对超大数取余
int numDecodings(string s) { int n = s.size(), M = 1e9 + 7; vector<long> dp(n + 1, 0); dp[0] = 1; if (s[0] == '0') return 0; dp[1] = (s[0] == '*') ? 9 : 1; for (int i = 2; i <= n; ++i) { if (s[i - 1] == '0') { if (s[i - 2] == '1' || s[i - 2] == '2') { dp[i] += dp[i - 2]; } else if (s[i - 2] == '*') { dp[i] += 2 * dp[i - 2]; } else { return 0; } } else if (s[i - 1] >= '1' && s[i - 1] <= '9') { dp[i] += dp[i - 1]; if (s[i - 2] == '1' || (s[i - 2] == '2' && s[i - 1] <= '6')) { dp[i] += dp[i - 2]; } else if (s[i - 2] == '*') { dp[i] += (s[i - 1] <= '6') ? (2 * dp[i - 2]) : dp[i - 2]; } } else { // s[i - 1] == '*' dp[i] += 9 * dp[i - 1]; if (s[i - 2] == '1') dp[i] += 9 * dp[i - 2]; else if (s[i - 2] == '2') dp[i] += 6 * dp[i - 2]; else if (s[i - 2] == '*') dp[i] += 15 * dp[i - 2]; } dp[i] %= M; } return dp[n]; }https://github.com/cherryljr/LeetCode/blob/master/Decode%20Ways%20II.java
X. DP
https://discuss.leetcode.com/topic/95251/java-dp-o-n-time-and-o-1-space
The idea for DP is simple when using two helper functions
ways(i) -> that gives the number of ways of decoding a single character
and
ways(i, j) -> that gives the number of ways of decoding the two character string formed by i and j.
The actual recursion then boils down to :
ways(i) -> that gives the number of ways of decoding a single character
and
ways(i, j) -> that gives the number of ways of decoding the two character string formed by i and j.
The actual recursion then boils down to :
f(i) = (ways(i) * f(i+1)) + (ways(i, i+1) * f(i+2))
The solution to a string f(i), where i represents the starting index,
f(i) = no.of ways to decode the character at i, which is ways(i) + solve for remainder of the string using recursion f(i+1)
and
no.of ways to decode the characters at i and i+1, which is ways(i, i+1) + solve for remainder of the string using recursion f(i+2)
and
no.of ways to decode the characters at i and i+1, which is ways(i, i+1) + solve for remainder of the string using recursion f(i+2)
The base case is ,
return ways(s.charAt(i)) if(i == j)
The above recursion when implemented with a cache, is a viable DP solution, but it leads to stack overflow error, due to the depth of the recursion. So its better to convert to memoized version.
For the memoized version, the equation changes to
f(i) = ( f(i-1) * ways(i) ) + ( f(i-2) *ways(i-1, i) )
This is exactly the same as the previous recursive version in reverse,
The solution to a string f(i), where i represents the ending index of the string,
f(i) = solution to the prefix of the string f(i-1) + no.of ways to decode the character at i, which is ways(i)
and
solution to the prefix f(i-2) + no.of ways to decode the characters at i - 1 and i, which is ways(i-1, i)
and
solution to the prefix f(i-2) + no.of ways to decode the characters at i - 1 and i, which is ways(i-1, i)
public static int numDecodings(String s) {
long[] res = new long[2];
res[0] = ways(s.charAt(0));
if(s.length() < 2) return (int)res[0];
res[1] = res[0] * ways(s.charAt(1)) + ways(s.charAt(0), s.charAt(1));
for(int j = 2; j < s.length(); j++) {
long temp = res[1];
res[1] = (res[1] * ways(s.charAt(j)) + res[0] * ways(s.charAt(j-1), s.charAt(j))) % 1000000007;
res[0] = temp;
}
return (int)res[1];
}
private static int ways(int ch) {
if(ch == '*') return 9;
if(ch == '0') return 0;
return 1;
}
private static int ways(char ch1, char ch2) {
String str = "" + ch1 + "" + ch2;
if(ch1 != '*' && ch2 != '*') {
if(Integer.parseInt(str) >= 10 && Integer.parseInt(str) <= 26)
return 1;
} else if(ch1 == '*' && ch2 == '*') {
return 15;
} else if(ch1 == '*') {
if(Integer.parseInt(""+ch2) >= 0 && Integer.parseInt(""+ch2) <= 6)
return 2;
else
return 1;
} else {
if(Integer.parseInt(""+ch1) == 1 ) {
return 9;
} else if(Integer.parseInt(""+ch1) == 2 ) {
return 6;
}
}
return 0;
}https://discuss.leetcode.com/topic/95277/c-dp-o-n-time-o-1-space
- For any string s longer than 2, we can decode either the last 2 characters as a whole or the last 1 character. So dp[i] = dp[i-1]* f(s.substr(i,1)) + dp[i-2]* f(s.substr(i-1, 2)). f() is the number of ways to decode a string of length 1 or 2. f() could be 0, for example f("67").
- There is a lot of cases and corner cases for f(string s). For example, * cannot be '0', so ** has 15 instead of 16 possibilities, because "20" is excluded. But the time complexity is still O(n).
int numDecodings(string s) {
int n = s.size(), p = 1000000007;
// f2 is the answer to sub string ending at position i; Initially i = 0.
long f1 = 1, f2 = helper(s.substr(0,1));
// DP to get f2 for sub string ending at position n-1;
for (int i = 1; i < n; i++) {
long f3 = (f2*helper(s.substr(i, 1)))+(f1*helper(s.substr(i-1, 2)));
f1 = f2;
f2 = f3%p;
}
return f2;
}
private:
int helper(string s) {
if (s.size() == 1) {
if (s[0] == '*') return 9;
return s[0] == '0'? 0:1;
}
// 11-26, except 20 because '*' is 1-9
if (s == "**")
return 15;
else if (s[1] =='*') {
if (s[0] =='1') return 9;
return s[0] == '2'? 6:0;
}
else if (s[0] == '*')
return s[1] <= '6'? 2:1;
else
// if two digits, it has to be in [10 26]; no leading 0
return stoi(s) >= 10 && stoi(s) <= 26? 1:0;
}int M = 1000000007; public int numDecodings(String s) { long[] dp = new long[s.length() + 1]; dp[0] = 1; dp[1] = s.charAt(0) == '*' ? 9 : s.charAt(0) == '0' ? 0 : 1; for (int i = 1; i < s.length(); i++) { if (s.charAt(i) == '*') { dp[i + 1] = 9 * dp[i]; if (s.charAt(i - 1) == '1') dp[i + 1] = (dp[i + 1] + 9 * dp[i - 1]) % M; else if (s.charAt(i - 1) == '2') dp[i + 1] = (dp[i + 1] + 6 * dp[i - 1]) % M; else if (s.charAt(i - 1) == '*') dp[i + 1] = (dp[i + 1] + 15 * dp[i - 1]) % M; } else { dp[i + 1] = s.charAt(i) != '0' ? dp[i] : 0; if (s.charAt(i - 1) == '1') dp[i + 1] = (dp[i + 1] + dp[i - 1]) % M; else if (s.charAt(i - 1) == '2' && s.charAt(i) <= '6') dp[i + 1] = (dp[i + 1] + dp[i - 1]) % M; else if (s.charAt(i - 1) == '*') dp[i + 1] = (dp[i + 1] + (s.charAt(i) <= '6' ? 2 : 1) * dp[i - 1]) % M; } } return (int) dp[s.length()]; }we can observe that only the last two values and are used to fill the entry at
public int numDecodings(String s) { long first = 1, second = s.charAt(0) == '*' ? 9 : s.charAt(0) == '0' ? 0 : 1; for (int i = 1; i < s.length(); i++) { long temp = second; if (s.charAt(i) == '*') { second = 9 * second; if (s.charAt(i - 1) == '1') second = (second + 9 * first) % M; else if (s.charAt(i - 1) == '2') second = (second + 6 * first) % M; else if (s.charAt(i - 1) == '*') second = (second + 15 * first) % M; } else { second = s.charAt(i) != '0' ? second : 0; if (s.charAt(i - 1) == '1') second = (second + first) % M; else if (s.charAt(i - 1) == '2' && s.charAt(i) <= '6') second = (second + first) % M; else if (s.charAt(i - 1) == '*') second = (second + (s.charAt(i) <= '6' ? 2 : 1) * first) % M; } first = temp; } return (int) second; }Approach #2 Recursion with memoization [Stack Overflow]
public int numDecodings(String s) { Integer[] memo=new Integer[s.length()]; return ways(s, s.length() - 1,memo); } public int ways(String s, int i,Integer[] memo) { if (i < 0) return 1; if(memo[i]!=null) return memo[i]; if (s.charAt(i) == '*') { long res = 9 * ways(s, i - 1,memo); if (i > 0 && s.charAt(i - 1) == '1') res = (res + 9 * ways(s, i - 2,memo)) % M; else if (i > 0 && s.charAt(i - 1) == '2') res = (res + 6 * ways(s, i - 2,memo)) % M; else if (i > 0 && s.charAt(i - 1) == '*') res = (res + 15 * ways(s, i - 2,memo)) % M; memo[i]=(int)res; return memo[i]; } long res = s.charAt(i) != '0' ? ways(s, i - 1,memo) : 0; if (i > 0 && s.charAt(i - 1) == '1') res = (res + ways(s, i - 2,memo)) % M; else if (i > 0 && s.charAt(i - 1) == '2' && s.charAt(i) <= '6') res = (res + ways(s, i - 2,memo)) % M; else if (i > 0 && s.charAt(i - 1) == '*') res = (res + (s.charAt(i)<='6'?2:1) * ways(s, i - 2,memo)) % M; memo[i]= (int)res; return memo[i]; }
下面这种解法是论坛上排名最高的解法，常数级的空间复杂度，写法非常简洁，思路也巨牛逼，博主是无论如何也想不出来的，只能继续当搬运工了。这里定义了一系列的变量e0, e1, e2, f0, f1, f2。其中：
e0表示当前可以获得的解码的次数，当前数字可以为任意数 (也就是上面解法中的dp[i])
e1表示当前可以获得的解码的次数，当前数字为1
e2表示当前可以获得的解码的次数，当前数字为2
f0, f1, f2分别为处理完当前字符c的e0, e1, e2的值
那么下面我们来进行分类讨论，当c为星号的时候，f0的值就是9*e0 + 9*e1 + 6*e2，这个应该不难理解了，可以参考上面解法中的讲解，这里的e0就相当于dp[i-1]，e1和e2相当于两种不同情况的dp[i-2]，此时f1和f2都赋值为e0，因为要和后面的数字组成两位数的话，不会增加新的解码方法，所以解码总数跟之前的一样，为e0, 即dp[i-1]。
当c不为星号的时候，如果c不为0，则f0首先应该加上e0。然后不管c为何值，e1都需要加上，总能和前面的1组成两位数；如果c小于等于6，可以和前面的2组成两位数，可以加上e2。然后我们更新f1和f2，如果c为1，则f1为e0；如果c为2，则f2为e0。
最后别忘了将f0，f1，f2赋值给e0，e1，e2，其中f0需要对超大数取余，参见代码如下：
有细心的朋友问了, 为什么
f0 = 9 * e0 + 9 * e1 + 6 * e2; 是 9.
因为是题目里面说, number只能是从1-9.
Beyond that, now the encoded string can also contain the character '*', which can be treated as one of the numbers from 1 to 9.
int numDecodings(string s) { long e0 = 1, e1 = 0, e2 = 0, f0, f1, f2, M = 1e9 + 7; for (char c : s) { if (c == '*') { f0 = 9 * e0 + 9 * e1 + 6 * e2; f1 = e0; f2 = e0; } else { f0 = (c > '0') * e0 + e1 + (c <= '6') * e2; f1 = (c == '1') * e0; f2 = (c == '2') * e0; } e0 = f0 % M; e1 = f1; e2 = f2; } return e0; }
下面这解法由热心网友edyyy提供，在解法二的基础上去掉了两个变量，节省了行数
int numDecodings(string s) { long e0 = 1, e1 = 0, e2 = 0, f0 = 0, M = 1e9 + 7; for (char c : s) { if (c == '*') { f0 = 9 * e0 + 9 * e1 + 6 * e2; e1 = e0; e2 = e0; } else { f0 = (c > '0') * e0 + e1 + (c <= '6') * e2; e1 = (c == '1') * e0; e2 = (c == '2') * e0; } e0 = f0 % M; } return e0; }
