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
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]]
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)