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];
}
}
做過的題目 上次是用法三解
這次練習用遞迴解解看
告辭