Decode Ways

Prereq: Memoization Intro

We have a message to decode. Letters are encoded to digits by their positions in the alphabet

1A -> 1
2B -> 2
3C -> 3
4...
5Y -> 25
6Z -> 26

Given a non-empty string of digits, how many ways are there to decode it?

Input: "18"

Output: 2

Explanation: "18" can be decoded as "AH" or "R"

Input: "123"

Output: 3

Explanation: "123" can be decoded as "ABC", "LC", "AW"

Try it yourself

Explanation

Combinatorial search problem, apply the three-step system:

1. Identify states

What state do we need to know whether we have decoded a string?

  1. We can keep track of the number of digits we have already matched in index i. When i == length of digits, we have finished.

What state do we need to decide which child nodes of the state-space tree should be visited next?

Since there's no constraint on which letters can be used for decoding, we don't need any state here.

2. Draw the space-state tree

3. DFS

Using the backtracking template as a basis, we add the state we identified in step 1:

  1. i for the number of digits we have already matched.

DFS returns the number of ways we can decode digits[i:].

Time Complexity: O(2^n)

n is the length of the string. Essentially at every digit we either make a new number or add it to the old one. We can make this into linear time through dp but currently we have a exponential time solution.

1def decode_ways(digits):
2    # use numbers 1 to 26 to represent all alphabet letters
3    prefixes = [str(i) for i in range(1, 27)]
4
5    def dfs(start_index):
6        if start_index == len(digits):
7            return 1
8
9        ways = 0
10        remaining = digits[start_index:]
11        for prefix in prefixes:
12            if remaining.startswith(prefix):
13                ways += dfs(start_index + len(prefix)) # add number of ways returned from child node
14
15        return ways
16
17    return dfs(0)
18

Again, we see there are overlapping subproblems.

Add memoization:

1
1
1def decode_ways(digits):
2
2
1    prefixes = [str(i) for i in range(1, 27)]
3
3
4
-
1    def dfs(start_index):
4
+
1    def dfs(start_index, memo):
5
+
1        if start_index in memo:
6
+
1            return memo[start_index]
7
+
5
8
1        if start_index == len(digits):
6
9
1            return 1
7
10
8
11
1        ways = 0
Expand 1 lines ...
10
13
1        for prefix in prefixes:
11
14
1            if remaining.startswith(prefix):
12
-
1                ways += dfs(start_index + len(prefix))
15
+
1                ways += dfs(start_index + len(prefix), memo)
13
16
14
17
18
+
1        memo[start_index] = ways
15
19
1        return ways
16
20
17
-
1    return dfs(0)
21
+
1    return dfs(0, {})