递归+回溯 枚举
枚举方法只有两种,选当前一个数,还是选取两个数(<=26)。
dfs状态:dfs(int k, String s)。k表示当前还剩几个数需要选。
class Solution {
int ans = 0;
public int numDecodings(String s) {
ans = 0;
dfs(s.length(), s);
return ans;
}
public void dfs(int k, String s) {
if (k <= 0) {
ans++;
return;
}
// 如果当前数为0,此路不通。(上个状态必须拼成10或20)
if (s.charAt(s.length() - k) == '0') return;
for (int i = 1; i <= 2; i++) {
if (i == 1) {
dfs(k - 1, s);
} else if (k > 1) {
if (s.charAt(s.length() - k) == '1') {
dfs(k - 2, s);
} else if (s.charAt(s.length() - k) == '2' &&
s.charAt(s.length() - k + 1) >= '0' && s.charAt(s.length() - k + 1) <= '6') {
dfs(k - 2, s);
}
}
}
}
}