Find all possible combinations of a String representation of a number

algorithm, combinations, dynamic

Solution

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.

Problem

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

Original source