91. Decode Ways (Medium)
A message containing letters fromA-Zis 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.
Solution 1: DP O(n); O(n)
/**
* DP O(n);O(n)
* Fibonacci sequence的变形版，只不过要考虑两个限制条件。
* Suppose the length of the String is n.
* Recurrence relation:
* number of decode ways at length n related to number of decode ways at previous lengths.
* Decode the single last digit, if the digit is not 0, then ways[n] += ways[n-1].
* Decode the last two digits, if possible, then ways[n] += ways[n-2].
* Base cases:
* ways[0] = 1, means only one way when string length is 0. If it is 0, ways[2] can be wrong.
* ways[1] = 0 or 1, depending on the only digit is 0 or not.
*
* dp[i] means the number of ways to decode first i chars, so the size of array is n + 1.
* dp[0] means an empty string will have one way to decode, dp[1] means the way to decode a string of size 1.
* Then check one digit and two-digit combination and save the results along the way.
* In the end, dp[n] will be the result.
*/
public int numDecodings(String s) {
if (s == null || s.length() == 0 || s.charAt(0) == '0') {
return 0;
}
int n = s.length();
int[] dp = new int[n + 1];
//https://discuss.leetcode.com/topic/35840/java-clean-dp-solution-with-explanation/16
dp[0] = 1; //只是为了后续递推计算而赋值，没有实际意义
dp[1] = 1; //dp[1] = s.charAt(0) == '0' ? 0 : 1; //直接在异常检测处返回更好
for (int i = 2; i <= n; i++) { //s.charAt(i - 1)是当前字符串
if (s.charAt(i - 1) != '0') { //高效简洁 //int first = Integer.valueOf(s.substring(i - 1, i));
dp[i] = dp[i - 1]; //s.charAt(i - 1) is decoded as one char.
}
int two = Integer.valueOf(s.substring(i - 2, i)); //面试用这种
//用下面写法效率更高
//int two = s.charAt(i - 1) - '0' + (s.charAt(i - 2) - '0') * 10;
if (two >= 10 && two <= 26) {
dp[i] += dp[i - 2]; //the last two digits are decoded as one char.
}
}
return dp[n];
}
Solution 2: DP O(n); O(1)
/**
* DP. Bottom-up. Space Optimized.
* O(n) Time, O(1) Space.
* Don't need an array since we only need previous two results.
* Must keep the previous two results up-to-date during iteration.
*/
public int numDecodingsB(String s) {
if (s == null || s.length() == 0 || s.charAt(0) == '0') {
return 0;
}
int pre = 1;
int cur = 1;
for (int i = 2; i <= s.length(); i++) {
int temp = cur;
cur = s.charAt(i - 1) != '0' ? cur : 0;
int two = s.charAt(i - 1) - '0' + (s.charAt(i - 2) - '0') * 10;
cur += two >= 10 && two <= 26 ? pre : 0;
pre = temp;
}
return cur;
}
Follow Up:
- 如果给的value不连续，比如a:78, b:539, ..., 怎么办。。我说可以backtracking，然后简单说了一下怎么搞。 还可以用dp，每次判断一个新的string的时候，例如判断123456， 可以遍历26个字母对应的每个number， 看该number能否作为这个String的结尾， 如果可以，就可以写dp[i] += dp[i-L]， 由于String每次前进一位只要遍历26次，所以复杂度还是O(n)。
(A)Return all decode ways
public List<String> numDecodingsC(String s) { List<String> res = new ArrayList<>(); if (s == null || s.length() == 0) return res; dfs(res, s, new StringBuilder(), 0); return res; } private void dfs(List<String> res, String s, StringBuilder sb, int i) { if (i == s.length()) {//if the whole string has been decoded, return 1 res.add(sb.toString()); return; } if (s.charAt(i) == '0') return; int len = sb.length(); int num1 = Integer.valueOf(s.substring(i, i + 1)); dfs(res, s, sb.append((char) ('A' + num1 - 1)), i + 1); sb.setLength(len); if (i < s.length() - 1 && Integer.valueOf(s.substring(i, i + 2)) <= 26) { int num2 = Integer.valueOf(s.substring(i, i + 2)); dfs(res, s, sb.append((char) ('A' + num2 - 1)), i + 2); sb.setLength(len); } }把input的string里面加上一些*符号，这些*符号可以代表0~9之间任意一个数字，求此时的decode ways。http://www.1point3acres.com/bbs/thread-230947-1-1.html