91. Decode Ways
该题提供一个由数字组成的字串s，并提供我们一个编码表：
'A' -> "1"
'B' -> "2"
...
'Z' -> "26"
求出s共有几种编码的方式，若无法被编码出来返回0。
Example：
Input: s = "12"
Output: 2
Explanation: "12" could be decoded as "AB" (1 2) or "L" (12).
解法一 递回穷举
思路：
1.每个字串每次都有两个选择，分别是一个一个切和两个两个切，递回树如下所示：
https://i.imgur.com/InBW19F.png
2.当遇到下列情况时，表示当前的字串无法继续解析：
＞ 字串长度为1且数字 < 1 （0）
＞ 字串长度为2且第一位数 < 1 或 > 2 （06, 38, 46, ...）
＞ 字串长度为2且第二位数 > 6 （27, 28, 29）
3.依据第二点之条件，不断的把字串切分，当切到最后一个字串时，表示这个切分
是合法的，res递增
4.返回res
Java Code：
class Solution {
public int numDecodings(String s) {
return s.length() == 0 ? 0 : numDecodings(s, 0);
}
private int numDecodings(String s, int start) {
int n = s.length();
if(start == n) return 1;
if(s.charAt(start) == '0') return 0;
int res = numDecodings(s, start + 1);
if(start < n - 1 && (s.charAt(start) == '1' ||
s.charAt(start) == '2' && s.charAt(start + 1) < '7'))
res += numDecodings(s,start + 2);
return res;
}
}
结果：TLE
解法二 内存最佳化
1.法一的递回过程有太多的重复计算，例如对于字串1111111，我们会重复算多次111, 11
11, 11, ...等等
2.利用一个momo储存已经算过的区段
Java Code：
class Solution {
Integer[] memo;
public int numDecodings(String s) {
memo = new Integer[s.length()];
return s.length() == 0 ? 0 : numDecodings(s, 0);
}
private int numDecodings(String s, int start) {
int n = s.length();
if(start == n) return 1;
if(s.charAt(start) == '0') return 0;
if(memo[start] != null) return memo[start];
int res = numDecodings(s, start + 1);
if(start < n - 1 && (s.charAt(start) == '1' ||
s.charAt(start) == '2' && s.charAt(start + 1) < '7'))
res += numDecodings(s,start + 2);
return memo[start] = res;
}
}
解法三 Button up
1.与法二概念类似，推导出状态转移方程后，直接iterative求得解
Java Code：
class Solution {
public int numDecodings(String s) {
if (s.charAt(0) == '0') return 0;
char[] chars = s.toCharArray();
int n = chars.length;
int[] dp = new int[n + 1];
dp[0] = 1;
for (int i = 1; i < dp.length; ++i) {
dp[i] = chars[i - 1] == '0' ? 0 : dp[i - 1];
if (i > 1 && (chars[i - 2] == '1'
|| (chars[i - 2] == '2' && chars[i - 1] < '7'))) {
dp[i] += dp[i - 2];
}
}
return dp[n];
}
}
做过的题目 上次是用法三解
这次练习用递回解解看
告辞