I solved a practice interview problem that was sent me by Daily Coding Problem mailing list. I am now curious about the exact time complexity of my solution.
Problem Statement
Given the mapping a = 1, b = 2, ... z = 26, and an encoded message, count the number of ways it can be decoded.
For example, the message '111' would give 3, since it could be decoded as 'aaa', 'ka', and 'ak'. You can assume that the messages are decodable. For example, '001' is not allowed.
I made an assumption that my solution should accept any type of mapping, not just the one mentioned in the question. So the running time of the algorithm is parametrized by the encoded message length and the type of mapping used.
Attempted Solution
class Node:
def __init__(self, val):
self.val = val
self.children = []
def add_child(self, child):
self.children.append(child)
def count_encodings(cipher, mapping):
# what is the longest possible map value
longest_val = max([len(str(x)) for x in mapping.values()])
root = Node('')
create_cipher_subtree(root, cipher, longest_val, mapping)
return count_leaves(root)
def create_cipher_subtree(node, cipher, longest_val, mapping):
for part_len in range(1, min(longest_val, len(cipher)) + 1):
curr_part = cipher[:part_len]
if curr_part in mapping.values():
child = Node(curr_part)
node.add_child(child)
remaining_part = cipher[part_len:]
if remaining_part:
create_cipher_subtree(child, remaining_part, longest_val, mapping)
def count_leaves(node):
if not node.children:
return 1
count = 0
for child in node.children:
count += count_leaves(child)
return count
We can then reproduce the example solution as follows:
from string import ascii_lowercase
mapping = {k: str(v) for v, k in enumerate(ascii_lowercase)}
cipher = '111'
print(count_encodings(cipher, mapping))
In short, this solution constructs a tree, like this:
''
'1' '11'
'1' '11' '1'
'1'
Then the number of leaf nodes is counted.
Explanation
First, the algorithm checks all possible values in the mapping and records the length of the longest value (longest_val
).
We then create a tree, where each node's val
field is a part of the encoded message (cipher
) that corresponds to a single mapping value; the root is the only node which has val
as empty string. Concatenation of nodes' val
fields along the path from the root to a leaf is one possible way of encoding.
The tree is created as follows:
- Check if the first character of
cipher
can be interpreted as a mapping value. - If yes, create a node with that value recorded and make it a child of root. Then, pass the rest of the
remaining_part
of the encoded message (everything past the first character) to the child and repeat the process from there. - Check if the first two characters of
cipher
can be interpreted as a mapping value. - Repeat step 2, but now
val
is two characters. Theremaining_part
would be everything in the encoded message past the first two values. This would create another child node of root. - If
longest_val
was 3, we would then check if the first 3 characters ofcipher
can be interpreted as a mapping value.... And so on.
After the tree is created, we count the number of leaf nodes, which corresponds to number of possible messages that can produce the provided encoding.
Complexity Analysis
I know that creating the tree of all possible ways the message could have been encoded might have been an overkill for this problem (in terms of space use), but doing it this way helped me better reason about the solution.
I am now unsure about the exact relation between a mapping choice and message length, and the answer to the question. What is the time complexity of this solution?
I am more interested in how various mappings affect the complexity. E.g. if some of the values in the mapping were 3-digit numbers, then many nodes in the tree would have 3 children. Does this increase the complexity of the algorithm? How would one capture this fact when writing Big-Oh expression for the algorithm?