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]

Evoke

DO you have to print all possible combinations or number of possible combinations? – Pullulate

What if input is 101? Does it split into 10,1 and 1,01? – Oversexed

@Fallen: number of possible combinations – Evoke

Jason, you are right. – Evoke

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.

Womanhater

Dukeling, your solution got me started thinking in the right direction. I do, have some objections in the main logic in your code. Why are you looking at the elements at [i-2] and [i-1]? Should you not be looking at input[i-1] and input[i] to check whether input[i-1...i] lies in [1,26]? I have updated my question to propose a solution that I could think of based on your code here. Can you please comment on that? – Evoke

i-2 and i-1 versus i-1 and i are essentially the same. For my solution, A[0] is for an array with 0 elements, yours is for 1 element, both approaches are valid. For your solution - A[i-1]*10 + A[i] should be input[i-1]*10 + input[i], A is you DP array, not the input. For 109, you'll count 0 and 09, but neither are valid - you need to include additional checks (as I did). A[i] += 1 is not correct. You can't just increase by 1, e.g for 1912, your A will be [1,2,2,3], but it should be [1,2,2,4], you need to add the number of representations using 2 less characters. – Womanhater

great explanation. I have posted a java based solution to this question based on our discussion below. – Evoke

Answer does count solutions with a leading zero, or with more than 1 leading zeros: 1001. – Geithner

@BernhardBarker Could you please give outline of a recursive program that could help print the combinations? – Gesellschaft

Answer 2

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.

Epicurean

Answer 3

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", "")

Tightrope

Answer 4

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.

Oversexed

Answer 5

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"]

Demand

Answer 6

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];
}

Evoke

Answer 7

Just us breadth-first search.

for instance 121

Start from the first integer, consider 1 integer character first, map 1 to a, leave 21 then 2 integer character map 12 to L leave 1.

Estrous

Answer 8

This problem can be done in o(fib(n+2)) time with a standard DP algorithm. We have exactly n sub problems and button up we can solve each problem with size i in o(fib(i)) time. Summing the series gives fib (n+2).

If you consider the question carefully you see that it is a Fibonacci series. I took a standard Fibonacci code and just changed it to fit our conditions.

The space is obviously bound to the size of all solutions o(fib(n)).

Consider this pseudo code:

Map<Integer, String> mapping = new HashMap<Integer, String>();

List<String > iterative_fib_sequence(string input) {
    int length = input.length;
    if (length <= 1) 
    {
        if (length==0)
        {
            return "";
        }
        else//input is a-j
        {
            return mapping.get(input);
        }
    }
    List<String> b = new List<String>();
    List<String> a = new List<String>(mapping.get(input.substring(0,0));
    List<String> c = new List<String>();

    for (int i = 1; i < length; ++i) 
    {
        int dig2Prefix = input.substring(i-1, i); //Get a letter with 2 digit (k-z)
        if (mapping.contains(dig2Prefix))
        {
            String word2Prefix = mapping.get(dig2Prefix);           
            foreach (String s in b)
            {
                c.Add(s.append(word2Prefix));
            }
        }

        int dig1Prefix = input.substring(i, i); //Get a letter with 1 digit (a-j)
        String word1Prefix = mapping.get(dig1Prefix);           
        foreach (String s in a)
        {
            c.Add(s.append(word1Prefix));
        }

        b = a;
        a = c;
        c = new List<String>();
    }
    return a;
}

Yukikoyukio

Answer 9

^{old question but adding an answer so that one can find help}

It took me some time to understand the solution to this problem – I refer accepted answer and @Karthikeyan's answer and the solution from geeksforgeeks and written my own code as below:

To understand my code first understand below examples:

• we know, decodings([1, 2]) are "AB" or "L" and so decoding_counts([1, 2]) == 2
• And, decodings([1, 2, 1]) are "ABA", "AU", "LA" and so decoding_counts([1, 2, 1]) == 3

using the above two examples let's evaluate decodings([1, 2, 1, 4]):

• case:- "taking next digit as single digit"

  taking 4 as single digit to decode to letter 'D', we get decodings([1, 2, 1, 4]) == decoding_counts([1, 2, 1]) because [1, 2, 1, 4] will be decode as "ABAD", "AUD", "LAD"

• case:- "combining next digit with the previous digit"

  combining 4 with previous 1 as 14 as a single to decode to letter N, we get decodings([1, 2, 1, 4]) == decoding_counts([1, 2]) because [1, 2, 1, 4] will be decode as "ABN" or "LN"

Below is my Python code, read comments

def decoding_counts(digits):
    # defininig count as, counts[i] -> decoding_counts(digits[: i+1])
    counts = [0] * len(digits)

    counts[0] = 1
    for i in xrange(1, len(digits)):

        # case:- "taking next digit as single digit"
        if digits[i] != 0: # `0` do not have mapping to any letter
            counts[i] = counts[i -1]

        # case:- "combining next digit with the previous digit"
        combine = 10 * digits[i - 1] + digits[i]
        if 10 <= combine <= 26: # two digits mappings
            counts[i] += (1 if i < 2 else counts[i-2])

    return counts[-1]

for digits in "13", "121", "1214", "1234121":
    print digits, "-->", decoding_counts(map(int, digits))

outputs:

13 --> 2
121 --> 3
1214 --> 5
1234121 --> 9

note: I assumed that input digits do not start with 0 and only consists of 0-9 and have a sufficent length

Cathe

note: decoding_counts([1, 3, 0]) --> 0 !! that is a bug – Cathe

Let me know if someone wants a complete execution example for "1214" according to decoding_counts() – Cathe

Answer 10

For Swift, this is what I came up with. Basically, I converted the string into an array and goes through it, adding a space into different positions of this array, then appending them to another array for the second part, which should be easy after this is done.

//test case
let input = [1,2,2,1]

func combination(_ input: String) {
    var arr = Array(input)
    var possible = [String]()

    //... means inclusive range
    for i in 2...arr.count {
        var temp = arr

        //basically goes through it backwards so 
        //  adding the space doesn't mess up the index
        for j in (1..<i).reversed() {
            temp.insert(" ", at: j)
            possible.append(String(temp))
        }
    }
    print(possible)
}

combination(input)

//prints: 
//["1 221", "12 21", "1 2 21", "122 1", "12 2 1", "1 2 2 1"]

Massproduce

Answer 11

 def stringCombinations(digits, i=0, s=''):

    if i == len(digits):
        print(s)
        return

    alphabet = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'
    total = 0

    for j in range(i, min(i + 1, len(digits) - 1) + 1):
        total = (total * 10) + digits[j]

        if 0 < total <= 26:
            stringCombinations(digits, j + 1, s + alphabet[total - 1])


if __name__ == '__main__':

    digits = list()
    n = input()
    n.split()
    d = list(n)
    for i in d:
        i = int(i)
        digits.append(i)
 
    print(digits)
stringCombinations(digits)

Silversmith