2
$\begingroup$

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:

  1. Check if the first character of cipher can be interpreted as a mapping value.
  2. 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.
  3. Check if the first two characters of cipher can be interpreted as a mapping value.
  4. Repeat step 2, but now val is two characters. The remaining_part would be everything in the encoded message past the first two values. This would create another child node of root.
  5. If longest_val was 3, we would then check if the first 3 characters of cipher 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?

$\endgroup$
  • $\begingroup$ Could you explain in words or pseudo-code what your algorithm is doing? It's hard to tell what the high-level overview of this python script does. It seems like from your example it does: 1) Can we take two digits for a proper encoding? 2) If yes, recurse on remaining $n-1$ digits and $n-2$ digits. 3) If no, recurse on remaining $n-1$ digits. Is this correct? $\endgroup$ – ryan Apr 2 at 0:36
  • $\begingroup$ Either way, if you are computing the decodings explicitly you can run into issues. Consider a string of $n$ 1's. At any point, we can decode it as 11 or two 1s. A simple lower bound is $2^{n/2}$ possible decodings. If you compute all of these it will be an exponential time algorithm. Also consider that your algorithm will create many redundant subtrees (e.g. try any encoding that starts with 11...). $\endgroup$ – ryan Apr 2 at 0:42
  • $\begingroup$ @ryan Your understanding is correct. I added a general description of the algorithm. After your comments, I am starting to think that some DP approach is probably more suitable for this kind of problem. Nevertheless, the original motivation for this question was to determine how different mappings would affect the time complexity of the algorithm. Please see the last paragraph. $\endgroup$ – Maxim Mikhaylov Apr 2 at 2:59
  • $\begingroup$ Yes, DP is probably the best approach as it can be computed in linear time. See my answer for some exponential lower bounds on your current implementation. $\endgroup$ – ryan Apr 2 at 18:29
2
$\begingroup$

You can show a simple exponential lower bound for you algorithm as follows.

  1. Assume we have a $d$ digit encoding (2 in your initial example).
  2. For any cipher text of length $n$ we can create a worst-case encoding of $n$ 1's.
  3. Now we divide the input into $n \ / \ d$ segments of length $d$.
  4. For any of these segments, we have $2^{d-1}$ ways of decoding it.
    • Take $d = 4$ for example, with a segment "1111" we have the following decodings:
      1. "1111"
      2. "1", "111"
      3. "1", "1", "11"
      4. "1", "1", "1", "1"
      5. "1", "11", "1"
      6. "11", "11"
      7. "11", "1", "1"
      8. "111", "1"
  5. Now we can decode all of these $n \ / \ d$ segments separately so we can multiply this together to get:

$$(2^{d-1})^{n/d} = 2^{(d-1)n/d}$$


You can get a tighter bound for this however by noting that the number of decodings for a string of ones is:

$$f(n) = \begin{cases} 1 & n = 1\\ 2 & n = 2\\ \vdots & \vdots\\ 2^{d-1} & n = d\\ \sum_{i = 1}^d f(n - i) \end{cases}$$

If we plug in for $d=2$ we actually see something familiar: $$f(n) = \begin{cases} 1 & n = 1\\ 2 & n = 2\\ f(n-1) + f(n-2) \end{cases}$$ This is the Fibonacci Sequence! This, we know is exponential in $n$. If you try $d=3$ you get the Tribonnaci Sequence. As you increase $d$ you simply get higher order Fibonacci sequences. All of these will be exponential in the worst case.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.