Find Number of Possible Alphabet Strings from Number Array

Question

Given a string 12345 and a alphabet to number mapping like a =1, b =2.., y=25, z=26; write a code to find the number of possible alphabet strings from the given string.

E.x. string 12345 has possible alphabet strings as {lcde,awde, abcde} from the mappings {12-3-4-5, 1-23-4-5, 1-2-3-4-5}.

I have a general idea of how to do it. I imagine it would be recursive. Look at the first digit and add it's char mapping to the result and then recurse with the sub array (1, size - 1). Also look at the two first digits and see if they are <= 26. If so, add that to the result and recurse (2, size - 2). Do this until number array is empty.

I get stuck on the actual implementation though. Is there a smarter way to do this than recursion?

Answer 1

This is similar to Word Break Problem. You can use same approach to solve it .you can use memoization to reduce overall running time. If you see in your given example:

12-3-4-5, 1-23-4-5, 1-2-3-4-5 

4 and 5 is getting repeated and you are calculating it again and again. You can store permutation of given index first time you calculated and use it later whenever you visit same index.

pseudo code:

recursive_function(string,index)
 if you have already calculated values for this index in previous call
    return value

 recursive_function(string,index+1)
 if possible 
   recursive_function(string,index+2) 

 store this value for future use.

Detail:

when you have recursive call for say index i ,when you are done with this call (basically returning from current recursion) you have already used/calculated/found all possible values (all permutation for sub-string starting at index i). you can store these values because if you will see there may be times when you will come again to index i from some other index sayj (j<i). so now this time you can return from this place itself instead of more recursive call for index i as you have already calculated values for index i and that will be same irrespective of j