Num Ways to Decode a Message - Backtracking / Aggregation and Memoization

Problems
29

I think something that would be beneficial on some of these more “clever” solutions is a simple walk through of what the code is doing. The observations about one vs two digit are helpful (and more or less obvious), but I am having an issue following the backtracking when the solution is finding a combination of one and two digit numbers. This has been the first problem where I’ve felt like I was having a hard time grokking what was going on. Even walking through the code in a debugger isn’t super helpful. It might be helpful, particularly when debugging, to include the path construction and printing out the different combinations like in other backtracking problems.

1 Like
30

I was messing around with the code for this to generate the path output and I believe this is it, which makes it easier for me to visualize and trace:

public class MessageDecodeMemo {

    public static int decode(String message) {
        List<List<String>> result = new ArrayList<>();
        decode(0, message, new ArrayList<>(), result);
        System.out.println(result);
        return result.size();
    }

    static int decode(int start, String message, List<String> path, List<List<String>> result) {
        if (start == message.length()) {
            result.add(List.of(String.join(",", path)));
            return 1;
        }
        int ways = 0;

        path.add(message.substring(start, start + 1));
        ways += decode(start + 1, message, path, result);
        path.removeLast();
        if (start + 2 <= message.length() && isValid(message.substring(start, start + 2))) {
            path.add(message.substring(start, start + 2));
            ways += decode(start + 2, message, path, result);
            path.removeLast();
        }

        return ways;
    }

    static boolean isValid(String candidate) {
        return Integer.parseInt(candidate) < 27 && Integer.parseInt(candidate) > 0;
    }
}

Examples:
input: “18”
output: [[1,8], [18]]

input: “123”
output: [[1,2,3], [1,23], [12,3]]

31

Possibly a more intuitive approach - although pretty similar to the official solution.

def decode_ways(digits):
    n = len(digits)
    memo = {}

    def dfs(start_index):
        if start_index in memo:
            return memo[start_index]
        if start_index == len(digits):
            return 1
        ways = 0
        for end in range(start_index + 1, n + 1):
            str_num = digits[start_index:end]
            if not str_num.startswith('0'):
                num = int(digits[start_index:end])
                if num > 0 and num < 27:
                    ways += dfs(end)
        memo[start_index] = ways
        return ways

    return dfs(0)