Find all possible combinations of a String representation of a number

Question

Given a mapping:

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

Find all possible ways a number can be represented. E.g. For an input: "121", we can represent it as:

ABA [using: 1 2 1]
LA [using: 12 1]
AU [using: 1 21]

I tried thinking about using some sort of a dynamic programming approach, but I am not sure how to proceed. I was asked this question in a technical interview.

Here is a solution I could think of, please let me know if this looks good:

A[i]: Total number of ways to represent the sub-array number[0..i-1] using the integer to alphabet mapping.

Solution [am I missing something?]:

A[0] = 1 // there is only 1 way to represent the subarray consisting of only 1 number
for(i = 1:A.size):
    A[i] = A[i-1]
    if(input[i-1]*10 + input[i] < 26):
        A[i] += 1
    end
end
print A[A.size-1]

Answer 1

To just get the count, the dynamic programming approach is pretty straight-forward:

A[0] = 1
for i = 1:n
  A[i] = 0
  if input[i-1] > 0                            // avoid 0
    A[i] += A[i-1];
  if i > 1 &&                          // avoid index-out-of-bounds on i = 1
      10 <= (10*input[i-2] + input[i-1]) <= 26 // check that number is 10-26
    A[i] += A[i-2];

If you instead want to list all representations, dynamic programming isn't particularly well-suited for this, you're better off with a simple recursive algorithm.

Answer 2

Here is the solution based on my discussion here:

private static int decoder2(int[] input) {
    int[] A = new int[input.length + 1];
    A[0] = 1;

    for(int i=1; i<input.length+1; i++) {
      A[i] = 0;
      if(input[i-1] > 0) {
        A[i] += A[i-1];
      }
      if (i > 1 && (10*input[i-2] + input[i-1]) <= 26) {
        A[i] += A[i-2];
      }
      System.out.println(A[i]);
    }
    return A[input.length];
}

Answer 3

First off, we need to find an intuitive way to enumerate all the possibilities. My simple construction, is given below.

 let us assume a simple way to represent your integer in string format.

   a1 a2 a3 a4 ....an, for instance in 121 a1 -> 1 a2 -> 2, a3 -> 1

Now,

We need to find out number of possibilities of placing a + sign in between two characters. + is to mean characters concatenation here.

a1 - a2 - a3 - .... - an, - shows the places where '+' can be placed. So, number of positions is n - 1, where n is the string length. 

Assume a position may or may not have a + symbol shall be represented as a bit. So, this boils down to how many different bit strings are possible with the length of n-1, which is clearly 2^(n-1). Now in order to enumerate the possibilities go through every bit string and place right + signs in respective positions to get every representations,

For your example, 121

   Four bit strings are possible 00 01 10 11
   1   2   1
   1   2 + 1
   1 + 2   1
   1 + 2 + 1

  And if you see a character followed by a +, just add the next char with the current one and do it sequentially to get the representation,

 x + y z a + b + c d

 would be (x+y) z (a+b+c) d  

Hope it helps.

And you will have to take care of edge cases where the size of some integer > 26, of course.

Answer 4

I think, recursive traverse through all possible combinations would do just fine:

mapping = {"1":"A", "2":"B", "3":"C", "4":"D", "5":"E", "6":"F", "7":"G", 
"8":"H", "9":"I", "10":"J", 
"11":"K", "12":"L", "13":"M", "14":"N", "15":"O", "16":"P", 
"17":"Q", "18":"R", "19":"S", "20":"T", "21":"U", "22":"V", "23":"W", 
"24":"A", "25":"Y", "26":"Z"}

def represent(A, B):
    if A == B == '':
        return [""]
    ret = []
    if A in mapping:
        ret += [mapping[A] + r for r in represent(B, '')]
    if len(A) > 1:
        ret += represent(A[:-1], A[-1]+B)
    return ret

print represent("121", "")

Answer 5

Assuming you only need to count the number of combinations.

Assuming 0 followed by an integer in [1,9] is not a valid concatenation, then a brute-force strategy would be:

Count(s,n)
    x=0
    if (s[n-1] is valid)
        x=Count(s,n-1)
    y=0
    if (s[n-2] concat s[n-1] is valid)
        y=Count(s,n-2)
    return x+y

A better strategy would be to use divide-and-conquer:

Count(s,start,n)
    if (len is even)
    {
        //split s into equal left and right part, total count is left count multiply right count
        x=Count(s,start,n/2) + Count(s,start+n/2,n/2);
        y=0;
        if (s[start+len/2-1] concat s[start+len/2] is valid)
        {
            //if middle two charaters concatenation is valid
            //count left of the middle two characters
            //count right of the middle two characters
            //multiply the two counts and add to existing count
            y=Count(s,start,len/2-1)*Count(s,start+len/2+1,len/2-1);
        }
        return x+y;
    }
    else
    {
        //there are three cases here:

        //case 1: if middle character is valid, 
        //then count everything to the left of the middle character, 
        //count everything to the right of the middle character,
        //multiply the two, assign to x
        x=...

        //case 2: if middle character concatenates the one to the left is valid, 
        //then count everything to the left of these two characters
        //count everything to the right of these two characters
        //multiply the two, assign to y
        y=...

        //case 3: if middle character concatenates the one to the right is valid, 
        //then count everything to the left of these two characters
        //count everything to the right of these two characters
        //multiply the two, assign to z
        z=...

        return x+y+z;
    }

The brute-force solution has time complexity of T(n)=T(n-1)+T(n-2)+O(1) which is exponential.

The divide-and-conquer solution has time complexity of T(n)=3T(n/2)+O(1) which is O(n**lg3).

Hope this is correct.

Answer 6

Something like this?

Haskell code:

import qualified Data.Map as M
import Data.Maybe (fromJust)

combs str = f str [] where
  charMap = M.fromList $ zip (map show [1..]) ['A'..'Z']
  f []     result = [reverse result]
  f (x:xs) result
    | null xs = 
        case M.lookup [x] charMap of
          Nothing -> ["The character " ++ [x] ++ " is not in the map."]
          Just a  -> [reverse $ a:result]
    | otherwise = 
        case M.lookup [x,head xs] charMap of
          Just a  -> f (tail xs) (a:result) 
                 ++ (f xs ((fromJust $ M.lookup [x] charMap):result))
          Nothing -> case M.lookup [x] charMap of
                       Nothing -> ["The character " ++ [x] 
                                ++ " is not in the map."]
                       Just a  -> f xs (a:result)

Output:

*Main> combs "121"
["LA","AU","ABA"]