decode string algorithm implementation for advice

Question

Working on below algorithm puzzle to decode a string containing numbers into characters. Post full problem statement and reference code. Actually I referred a few solutions, and it seems all solutions I found decode from back to the front, and I think decode from front to end should also be fine, just wondering if any special benefits or considerations why for this problem, it is better to decode from back to front? Thanks.

A message containing letters from A-Z is being encoded to numbers using the following mapping:

'A' -> 1 'B' -> 2 ... 'Z' -> 26 Given an encoded message containing digits, determine the total number of ways to decode it.

For example, Given encoded message "12", it could be decoded as "AB" (1 2) or "L" (12).

The number of ways decoding "12" is 2.

public class Solution {
    public int numDecodings(String s) {
        int n = s.length();
        if (n == 0) return 0;

        int[] memo = new int[n+1];
        memo[n]  = 1;
        memo[n-1] = s.charAt(n-1) != '0' ? 1 : 0;

        for (int i = n - 2; i >= 0; i--)
            if (s.charAt(i) == '0') continue;
            else memo[i] = (Integer.parseInt(s.substring(i,i+2))<=26) ? memo[i+1]+memo[i+2] : memo[i+1];

        return memo[0];
    }
}

thanks in advance, Lin

Answer 1

There will be no difference whether you decode the string from front-to-back or back-to-front if you break it into sub-strings and store their results.

This implements front-to-back approach:

def decode_string(st):
    result_dict = {st[0]:1}

    for i in xrange(2,len(st)+1):
        if int(st[i-1]) == 0:
            if int(st[i-2]) not in [1,2]:
                return "Not possible to decode"

            result_dict[st[:i]] = 0

        else:
            result_dict[st[:i]] = result_dict[st[:i-1]]

        if int(st[i-2:i]) < 27 and st[i-2] != '0':
            result_dict[st[:i]] = result_dict[st[:i]] + result_dict.get(st[:i-2],1)

    return result_dict[st]

print decode_string("125312")

result_dict contains all the possibilities for incremental sub-strings. Initialize with first character

Special check for '0' character because the only acceptable values for 0 are 10 and 20. So break from the loop if input contains something else

Then for each index check whether the combination with the previous index is a character (combination < 27) or not. If true, add the result of string upto index-2 to it.

Store the result of each incremental sub-string in the dictionary

Result:

The result_dict contains values like this:

{'12': 2, '12531': 3, '1': 1, '125312': 6, '125': 3, '1253': 3}

So result_dict[st] gives the required answer

Using Lists is a better idea

def decode_string(st):
    result_list = [1]
    for i in xrange(2,len(st)+1):
        if int(st[i-1]) == 0:
            if int(st[i-2]) not in [1,2]:
                return "Not possible to decode"

            result_list.append(0)

        else:
            result_list.append(result_list[i-2])

        if int(st[i-2:i]) < 27 and st[i-2] != '0':
            if i>2:
                result_list[i-1] = result_list[i-1] + result_list[i-3]
            else:
                result_list[i-1] = result_list[i-1] + 1
    print result_list
    return result_list[-1]

print decode_string("125312")