DecodeWays [source code]
public class DecodeWays {
static
/******************************************************************************/
class Solution {
public int numDecodings(String s) {
if (s.length () == 0)
return 0;
char[] chs = s.toCharArray ();
int[] dp = new int[chs.length];
dp[0] = chs[0] > '0' ? 1 : 0;
for (int i = 1; i < dp.length; i++) {
if (chs[i] > '0')
dp[i] += dp[i - 1];
if (chs[i - 1] > '0' && ((chs[i - 1] - '0') * 10 + chs[i] - '0' <= 26))
// if i-1..i are the first two digits, then this is actually the new base case: assign 1 rather than 0
dp[i] += i - 2 >= 0 ? dp[i - 2] : 1;
}
return dp[chs.length - 1];
}
}
/******************************************************************************/
public static void main(String[] args) {
DecodeWays.Solution tester = new DecodeWays.Solution();
String[] inputs = {
"0", "0",
"01", "0",
"12", "2",
"26", "2",
"27", "1",
};
for (int i = 0; i < inputs.length / 2; i++) {
String s = inputs[2 * i];
System.out.println (Printer.separator ());
int ans = Integer.parseInt (inputs[2 * i + 1]), output = tester.numDecodings (s);
System.out.printf ("%s -> %s, expected: %d\n",
s, Printer.wrap (output + "", output == ans ? 92 : 91), ans
);
}
}
}
AC rate很低, downvote比较高, 耐心做;
看到tag给的DP提示, 好像有思路? 写写看;
原来这个0是一个坑;
还是不够仔细, 知道是DP以后其实就挺简单了; 最后还是被break掉了几次; 速度是1ms (90%);
可以空间优化, 不复杂, 懒得写了;
没有editorial;
https://leetcode.com/problems/decode-ways/discuss/30357/DP-Solution-(Java)-for-reference
public class Solution {
public int numDecodings(String s) {
int n = s.length();
if (n == 0) return 0;
int[] memo = new int[n+1];
memo[n] = 1;
memo[n-1] = s.charAt(n-1) != '0' ? 1 : 0;
for (int i = n - 2; i >= 0; i--)
if (s.charAt(i) == '0') continue;
else memo[i] = (Integer.parseInt(s.substring(i,i+2))<=26) ? memo[i+1]+memo[i+2] : memo[i+1];
return memo[0];
}
}
跟我的思路其实没有太大的区别, 就是他用了两个改动, 一个是, 倒着扫, 这个感觉没什么区别; 另外一个就是他的index是用的dot system; 只能说也行吧, 毕竟是string问题; DP的每一个iteration就相当于是在move dot;
dot system现在应该很熟了, 如果还是不记得, 那就自己重新画一个index就行了, 反正记得chs[i - 1] dot[i] chs[i]
这个序列就行了, 这个告诉你怎么完成在两个array之间的index的转换计算;
I am trying to add some notes to the code to make everybody understand better. Take manky’s code as example. Assigning memo[n] = 1; means when the string is empty, there is only one answer. memo[n-1] = s.charAt(n-1) != '0' ? 1 : 0; means when there is only one character in the string, if this character is not 0, there will be an answer, or there will be no answer. Then it starts the dp portion. When we add a letter from the end of the string, if the first two letters <=26, we can get memo[n]=memo[n+1]+memo[n+2]. For example, the String now is “123xxxx” and we know all the result from 2. Because 12<26, we can make this string either"12"+“3xxxx” or 1+23xxxx which is exactly memo[n]=memo[n-1]+memo[n-2]. if the String is"32xxxx" memo[n]=memo[n+1]. if there are 0s in the string, we should skip it and look at the next character because there is no answer when the string begins with 0.
s = 123
build up from right =>
num_ways ("") => 1 (empty string can be represented by empty string) (i.e. num_ways[n] = 1) NOTE: only for build up with a valid string. Empty string on it's own doesn't need to be decoded.
num_ways ("3") => 1 (only one way), i.e. num_ways[n-1] = 1
num_ways ("23") => "23" or "2"-"3",
num_ways ("33") => "3""3"
num_ways ("123") => "12"(num_ways("3")) + "1"("num_ways("23")) (i.e. num_ways[i+2] + num_ways[i+1])
num_ways ("323") => "3"(num_ways("23")) (i.e. num_ways[i+1])so basically if s[i:i+1] (both included) <= 26,
num_ways[i+2] + num_ways[i+1]
else:
num_ways[i+1]case with 0:
num_ways ("103")
num_ways ("3") => 1 (only one way)
num_ways ("03") => 0 (can't decode 0)
num_ways ("003") => "00"(num_ways("3")) + "0"(num_ways("03")) => no way to decode "00" = 0 + 0
num_ways ("103") => "10"(num_ways("3")) + "1"(num_ways("03")) => num_ways[i+2] + num_waysi+1
num_ways ("1003") => "10"(num_ways("03")) + "1"(num_ways("003")) => same eq = 0(no way to decode "03") + 0(no way to decode 003)Therefore, if i = '0', let memo[i] = 0, also implements for a string where the ith character == '0', string[i:end] can be decoded in 0 ways.
https://leetcode.com/problems/decode-ways/discuss/30358/Java-clean-DP-solution-with-explanation
I used a dp array of size n + 1 to save subproblem solutions. 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.
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+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];
}
}
@ElaricY Thank you for the answer. I can see that we need dp[0] = 1 for the correct solution. Just want to clarify that dp[0] = 1 is just an initialization to make sure our solution works for all strings for lengths >= 2. The point I am trying to make is dp[0] is not the number of ways to decode an empty string, it is an initialization as strings with length 0 or 1 will not even enter the loop.
没错, 最开始的初始值, 在semiring问题当中初始化很重要;
discussion还有一个从Top-Down一直优化到O(1) space Bottom-Up的, 懒得看了, 就这么回事儿;
https://leetcode.com/problems/decode-ways/discuss/30451/Evolve-from-recursion-to-dp
我这个就已经是submission最优解了;
Problem Description
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.
For example,
Given encoded message "12", it could be decoded as "AB" (1 2) or "L" (12).
The number of ways decoding "12" is 2.
Difficulty:Medium
Total Accepted:160.3K
Total Submissions:792.2K
Contributor:LeetCode
Companies
facebookmicrosoftuber
Related Topics
stringdynamic programming
Similar Questions
Decode Ways II