639. Decode Ways II

639. Decode Ways II (DFS).java

    public int numDecodings(String s) {
        if (s == null || s.length() == 0) return 0;
        int[] result = new int[]{0};
        dfs(s, 0, 1, result);
        return result[0];
    }
    private void dfs(String s, int i, int count, int[] result) {
        if (i == s.length()) {
            count = count % 1000000007;
            result[0] = (result[0] + count) % 1000000007;
            return;
        }
        // 0 can't be the beginning of a string
        if (s.charAt(i) == '0') return;
        // if the first character is digit
        if (s.charAt(i) >= '1' && s.charAt(i) <= '9') {
            // treat as single digit
            dfs(s, i + 1, count, result);
            // treat as two digits
            if (i < s.length() - 1) {
                if ((s.charAt(i) == '1' && s.charAt(i + 1) >= '0' && s.charAt(i + 1) <= '9') || (s.charAt(i) == '2' && s.charAt(i + 1) >= '0' && s.charAt(i + 1) <= '6')) {
                    dfs(s, i + 2, count, result);
                } else if (s.charAt(i) == '1' && s.charAt(i + 1) == '*') {
                    dfs(s, i + 2, count * 9, result);
                } else if (s.charAt(i) == '2' && s.charAt(i + 1) == '*') {
                    dfs(s, i + 2, count * 6, result);
                }
            } 
        }
        // if the first character is *
        if (s.charAt(i) == '*') {
             // treat as single digit
            dfs(s, i + 1, count * 9, result);
            // treat as two digits
            if (i < s.length() - 1) {
                if (s.charAt(i + 1) >= '0' && s.charAt(i + 1) <= '6') {
                    dfs(s, i + 2, count * 2, result);
                } else if (s.charAt(i + 1) >= '7' && s.charAt(i + 1) <= '9') {
                    dfs(s, i + 2, count, result);
                } else if (s.charAt(i + 1) == '*') {
                    dfs(s, i + 2, count * 15, result);
                }
            }
        }
    }