欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

[leetcode] 91. 解码方法

程序员文章站 2022-07-05 16:19:16
...

91. 解码方法

递归+回溯 枚举

枚举方法只有两种,选当前一个数,还是选取两个数(<=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);
                }
            }
        }
    }
}