We have a message to decode. Letters are encoded to digits by their positions in the alphabet
1A -> 12B -> 23C -> 34...
5Y -> 256Z -> 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?
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:
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.
1defdecode_ways(digits):2# use numbers 1 to 26 to represent all alphabet letters3 prefixes = [str(i) for i inrange(1, 27)]
45defdfs(start_index):6if start_index == len(digits):
7return189 ways = 010 remaining = digits[start_index:]
11for prefix in prefixes:
12if remaining.startswith(prefix):
13 ways += dfs(start_index + len(prefix)) # add number of ways returned from child node1415return ways
1617return dfs(0)
18