/ Data Structure and Algorithms  

Leetcode 91. Decode Ways

Question



Each number corresponds to a letter. Given a string of numbers, need to know how many decoding methods. For example, 226 can have three decode ways, 2|2|6, 22|6, 2|26.

Similar Questions

Solution 1 - Recursion

It is easy to think of using recursion, turning big problems into smaller problems.

For example, 232232323232.

For the first letter we have two divisions.

2|32232323232 and 23|2232323232

Therefore, if we know that the decoding result of the right part 32232323232 is ans1 and that of 2232323232 is ans2, then the overall 232232323232 decoding result is ans1 + ans2.

If it is too hard to understand, think about this analogy.

If there are two roads from Melbourne to Brisbane, via Sydney and Canberra. There are 8 roads from Sydney to Brisbane, and 6 roads from Canberra to Brisbane. So there are 8 + 6 = 14 routes from Melbourne to Brisbane.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
public int numDecodings(String s) {
    return getResult(s, 0);
}

// start is the index of the char in 's'
private int getResult(String s, int start) {
    // reaching the end
    if (start == s.length()) {
        return 1;
    }

    if (s.charAt(start) == '0') {
        return 0;
    }

    // answer if divide the first index
    // e.g. if input （123）
    // answer1 is 1 + answer(2,3)
    // answer2 is 12 + answer(3)
    int answer1 = getResult(s, start + 1);
    int answer2 = 0;

    // only have answer2 if first 2 digit <= 26
    if (start < s.length() - 1) {
        int ten = (s.charAt(start) - '0') * 10;
        int one = s.charAt(start + 1) - '0';

        if (ten + one <= 26) {
            answer2 = getResult(s, start + 2);
        }
    }

    return answer1 + answer2;
}

Solution 2 - Recursion + Dynamic Programming

In solution 1, after calculating ans1 and then calculate ans2, some already calculated results will be recalculated, so we can use the memoization technique to calculate a result and save it.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
public int numDecodings(String s) {
    // map startIndex -> result
    HashMap<Integer, Integer> cache = new HashMap<>();
    return getResult(s, 0, cache);
}

// start is the index of the char in 's'
private int getResult(String s, int start, HashMap<Integer, Integer> cache) {
    // reaching the end
    if (start == s.length()) {
        return 1;
    }

    if (s.charAt(start) == '0') {
        return 0;
    }

    // check if calculated before
    int tempResult = cache.getOrDefault(start, -1);
    if (tempResult != -1) {
        return tempResult;
    }

    // answer if divide the first index
    // e.g. if input （123）
    // answer1 is 1 + answer(2,3)
    // answer2 is 12 + answer(3)
    int answer1 = getResult(s, start + 1, cache);
    int answer2 = 0;

    // only have answer2 if first 2 digit <= 26
    if (start < s.length() - 1) {
        int ten = (s.charAt(start) - '0') * 10;
        int one = s.charAt(start + 1) - '0';

        if (ten + one <= 26) {
            answer2 = getResult(s, start + 2, cache);
        }
    }

    // cache the result
    cache.put(start, ans1 + ans2);

    return answer1 + answer2;
}