Print possible strings created from a Number

Question

Given a 10 digit Telephone Number, we have to print all possible strings created from that. The mapping of the numbers is the one as exactly on a phone's keypad.

i.e. for 1,0-> No Letter for 2-> A,B,C

So for example, 1230 ADG BDG CDG AEG....

Whats the best solution in c/c++ to this problem?

Answer 1

I think a recursive solution would be good for this one. So something like:

def PossibleWords(numberInput, cumulative, results):
    if len(numberInput) == 0:
        results.append(cumulative)
    else:
        num = numberInput[0]
        rest = numberInput[1:]
        possibilities = mapping[num]
        if len(possibilities) == 0:
            PossibleWords(rest, cumulative, results)
        else:
            for p in possibilities:
                PossibleWords(rest, cumulative + p, results)

result = []
PossibleWords('1243543', '', result)

Answer 2

You're looking at 10 digits, with 3 or 4 letters per digit (assuming no 0s or 1s). 3**10 combinations = 59049 combinations minimum, more if you allow Q and Z. That's going to be a lot of paper, no matter how you do it.

Answer 3

No need to go recursive. Here is an example of an iterative approach to start with. It prints out all the possibilities, but you may not entirely like its behaviour. The catch is left for the reader to discover ;-)

string tab[10]={"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
string s="1201075384"; //input string

for(int mask=0;mask<1048576;mask++)//4^10, trying all the posibilities
{
  int m=mask;
  string cur="";
  for(int i=0;i<s.size();i++,m/=4)  
    if (m%4<tab[s[i]-'0'].size())
      cur+=tab[s[i]-'0'][m%4];
  cout<<cur<<endl;
}