Given an encoded message, count the number of ways it can be decoded

Question

You are given an encoded message containing only numbers. You are also provided with the following mapping

 A : 1
 B : 2
 C : 3
 ..
 Z : 26

Given an encoded message, count the number of ways it can be decoded.

eg: 12 can be decoded in 2 ways: (A,B) and (L)

I came up with the algorithm of accepting the numbers as a character of strings and then checking for each of its digit:

1.If the first digit of the string array is zero , return zero.

2.for each of its digit(i) from 1 to n perform:

   if str[i-1]>2 || (str[i-1]=='2' && str[i]>'6')
      return 0;

   if(str[i]==0)
      return 0;

Each time i try to encode the first digit in the message to a letter, or i can encode the first two digits into a letter if possible. When there is no way to encode like encountering a single ’0′, or encountering ’32′, simply return.

Can this problem be solved more efficiently?

Answer 1

Your current approximation to the problem is correct. Although, you need to be really careful that you are handling all the cases which it is not clear and this will make my answer a bit longer than needed.

A correct way to see this problem is from a Dynamic Programming perspective. Let's consider your input string as message and its length as n.

To decode a message of n characters, you need to know in how many ways you can decode message using n - 1 characters and a message using n - 2 characters. That is,

A message of n characters.

                                              1
          1   2   3   4   5   6   7   8   9   0   1
        +---+---+---+---+---+---+---+---+---+---+---+
message | 1 | 2 | 3 | 4 | 1 | 2 | 3 | 1 | 4 | 1 | 2 |
        +---+---+---+---+---+---+---+---+---+---+---+

Using a 1 digit and a message of n - 1 characters long.

                                              1
          1   2   3   4   5   6   7   8   9   0       1
        +---+---+---+---+---+---+---+---+---+---+   +---+
message | 1 | 2 | 3 | 4 | 1 | 2 | 3 | 1 | 4 | 1 | + | 2 |
        +---+---+---+---+---+---+---+---+---+---+   +---+

Using a 2 digits and a message of n - 2 characters long.

                                                  1
          1   2   3   4   5   6   7   8   9       0   1
        +---+---+---+---+---+---+---+---+---+   +---+---+
message | 1 | 2 | 3 | 4 | 1 | 2 | 3 | 1 | 4 | + | 1 | 2 |
        +---+---+---+---+---+---+---+---+---+   +---+---+

Now, you may ask yourself:

How do I calculate in how many ways you can decode message of n - 1 characters and of n - 2 characters?

It's actually in the same way. Eventually you will reduce it to its base case.

Let's say ways[n] its the number of ways you can decode message of n characters. Then, you can put ways[n] in this way,

ways[n] = ways[n - 1] + ways[n - 2]

(Since there is no clue how you'd define the number of ways for an empty string I considered it as 1.)

With proper constraints and base case,

• n = 0,

   ways[n] =  1
  

• n > 1 and message[n] is valid and message[n - 1:n] is valid,

   ways[n] = ways[n - 1] + ways[n - 2]
  

• n > 1 and message[n] is valid and message[n - 1:n] is not valid,

   ways[n] = ways[n - 1]
  

• n > 1 and message[n] is not valid and message[n - 1:n] is valid,

   ways[n] = ways[n - 2]
  

• otherwise,

   ways[n] = 0
  

An iterative decode function in C may look as follows,

int decode(char* message, size_t len) {
    int i, w, ways[] = { 1, 0 };
    for(i = 0, w; i < len; ++i) {
        w = 0;
        if((i > 0) && ((message[i - 1] == '1') || (message[i - 1] == '2' && message[i] < '7'))) {
            w += ways[1];
        }
        if(message[i] > '0') {
            w += ways[0];
        }
        ways[1] = ways[0];
        ways[0] = w;
    }
    return ways[0];
}

You can see it here at ideone. I'm using constant extra memory for the calculation.

Answer 2

Thought I'd complement @Alexander's post with my commented python code, as it took me a bit of time to get my head around exactly how the dynamic programming solution worked. I find it useful to realise how similar this is to coding the Fibonacci function. I've also uploaded full code, tests and runtime comparison with naive recursion on my github.

def number_of_decodings_fast(code):
    """ Dynamic programming implementation which runs in 
    O(n) time and O(1) space. 
    The implementation is very similar to the dynamic programming
    solution for the Fibonacci series. """
    length = len(code)
    if (length <= 1):
        # assume all such codes are unambiguously decodable
        return 1
    else:
        n_prev = 1 # len 0
        n_current = 1 # len 1
        for i in range(1,length):
            if (
                # a '1' is ambiguous if followed by
                # a digit X=[1-9] since it could be
                # decoded as '1X' or '1'+'X'
                code[i-1]=='1' and 
                code[1] in [str(k) for k in (range(1,10))]
            ) or (
                # a '2' is ambiguous if followed by 
                # a digit X=[1-6] since it could be
                # decoded as '2X' or '2'+'X'
                code[i-1]=='2' and 
                code[i] in [str(k) for k in range(1,7)]
            ):
                # New number of decodings is the sum of
                # decodings obtainable from the code two digits back
                # (code[0:(i-2)] + '[1-2]X' interpretation)
                # and decodings obtainable from the code one digit back
                # (code[0:(i-1)] + 'X' interpretation).
                n_new = n_prev + n_current
            else:
                # New number of decodings is the same as
                # that obtainable from the code one digit back
                # (code[0:(i-1)] + 'X' interpretation).
                n_new = n_current
            # update n_prev and n_current
            n_prev = n_current
            n_current = n_new
        return n_current