CareerCup

Could not understand the question properly. Is it like a number will be given, and we need to print all the possible word combinations ?
If so, this is a sample code (might not be an efficient sol, but it came to my mind first)

#include <stdio.h>

void printMnemonics(int count,char str[]);

/* Codes for 723 */
char A[][5]={{'P','Q','R','S','\0'},{'A','B','C','\0'},{'D','E','F','\0'}};
int level=3;

int main()
{
char str[5];

printMnemonics(0,str);

return 0;
}

void printMnemonics(int count,char str[])
{
int i;
if(count == level)
{
str[count]='\0';
printf("%s\n",str);
return;
}

i=0;
while(A[count][i] != '\0')
{
str[count]=A[count][i];
printMnemonics(count+1,str);
i++;
}
}

This problem needs to be solved Recursively.

Good one V !

public class Phone2Text {
	private static String[] mapping = { "ABC", "DEF", "GHI", "JKL", "MNO",
			"PQR", "STU", "VW", "XY", "Z*#" };

	public static void combinations(int[] number, char[] buf, int numIndex) {

		for (int i = 0; i < mapping[number[numIndex]].length(); i++) {
			buf[numIndex] = mapping[number[numIndex]].charAt(i);
			if (numIndex < number.length - 1) {
				combinations(number, buf, numIndex + 1);
			} else
				System.out.println(buf);
		}
	}

	public static void main(String[] args) {
		int num[] = { 5, 1, 2, 8, 6, 0, 7 };
		Phone2Text.combinations(num, new char[num.length], 0);
	}
}

Recursive solution is the most obvious. Here is an iterative one

The idea is to count for all the possible permutations. E.g. For number '237', the result would be combination of "abc", "def" and "pqrs" i.e. 3*3*4 combinations.
We can count from 000 to 223 (since index start from 0) and output the text based on each digits. The counting should be done carefullly, i.e. after 003, the next number 010 and after that 011, 012, 013, 020 and so on. At each count, we output the corresponding text i.e. for 012, we output/store ("abc"[0] + "def"[0] + "pqrs"[2] = "adr"). This ofcourse is exponential but is still better than costlier recursive solution. Here's a python code

import sys
letters = ["0", "1", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"]
num  = 237
num = str(num)
count = [0] * len(num)

def add_count():
    for i in xrange(len(count)):
        count[i] = count[i] + 1
        if(count[i] == len(letters [int(num[i])])):
            if(i == len(num) - 1):
                return False
            count[i] = 0
        else:
            return True


print ''.join(map(lambda x, y: letters[int(x)][y], num, count))
while(add_count()):
   print ''.join(map(lambda x, y: letters[int(x)][y], num, count))

Hi dear posters. First of all, I would like to mention that this is not a problem with permutation, but a problem of combinations with a set of possible values for each position in the number. Below is a complete application that generates all the possible words/word combinations for the given number map and the number. Hope the inline comments are quite self-descriptive.

#include <stdio.h>
#include <string.h>
static const int NUM_MAX_CHARS = 5;
struct char_keys {
    int key;
    int count;
    char chrs[NUM_MAX_CHARS];
};
/* Phone pad key mappings */
static char_keys s_keys[10] = {
    {0, 1, {'0',}            },
    {1, 1, {'1',}            },
    {2, 3, {'A','B','C'}    },
    {3, 3, {'D','E','F'}    },
    {4, 3, {'G','H','I'}    },
    {5, 3, {'J','K','L'}    },
    {6, 3, {'M','N','O'}    },
    {7, 4, {'P','Q','R','S'}},
    {8, 3, {'T','U','V'}    },
    {9, 4, {'W','X','Y','Z'}},
};
void print_key_map(int keystart, int keyend)
{
    int i, cnt;

    if (keystart > keyend)
        return;
    if (keystart < 0 || keyend < 0 || keystart > 9 || keyend > 9)
        return;

    for (i = keystart; i <= keyend; i++){
        char_keys *chk = &s_keys[i];
        printf("KEY %d: COUNT %d: ", i, chk->count);
        for (cnt = 0; cnt < chk->count; cnt++) {
            printf("%c", chk->chrs[cnt]);
        }
        printf("\n");
    }
}
inline char get_char_key(int key, int pos)
{
    char ret = 0;

    if (key < 0 || key > 9)
        return ret;
    if (pos < 0 || pos >= NUM_MAX_CHARS)
        return ret;
    ret = s_keys[key].chrs[pos];
    return ret;
}
void print_word(int num[], int idx[], int cnt)
{
    int i;
    char chrval;

    for (i = 0; i < cnt; i++) {
        chrval = get_char_key(num[i], idx[i]);
        printf("%c", chrval);
    }
    printf("\n");
}
int get_key_max_idx(int key)
{
    int rv;

    rv = s_keys[key].count - 1;
    return rv;
}
void gen_phone_words(int *nums, int cnt)
{
    int i, uidx, mxidx;
    int *pidx = NULL;
    bool bFinished = false;
    pidx = new int[cnt];
    if (NULL == pidx)
        return;
    for (i = 0; i < cnt; i++)
        pidx[i] = 0;
    uidx = cnt - 1;
    print_word(nums, pidx, cnt);    
    while (!bFinished) {
        /* Increment the last number's index */ 
        pidx[uidx]++;
        int carry = 0;
        for (i = uidx; i >= 0; i--){
            pidx[i] += carry;
            mxidx = get_key_max_idx(nums[i]);
            if (pidx[i] > mxidx){
                carry = 1;
                pidx[i] = 0; // On overflow, reset this index to its lowest value
                if (i == 0)
                    bFinished = true;
            }
            else {
                break;
            }
        }
        if (bFinished)
            break;
        print_word(nums, pidx, cnt);
    }
    delete [] pidx;
}

int* str_to_int_arr(char *str, int& cnt)
{
    int *ret, *tmp, i;
    int len;

    if (NULL == str)
        return NULL;

    len = (int) strlen(str);
    ret = new int[len];
    if (NULL == ret)
        return NULL;

    tmp = ret;
    for (i = 0; i < len; i++){
        *tmp++ = static_cast<int>(str[i] - '0');
        cnt++;
    }

    return ret;
}

int main(int argc, char* argv[])
{
    int *dat = NULL, cnt = 0;
    char num[100];

    if (argc > 1)
        strcpy(num, argv[1]);
    else
        strcpy(num, "363138");
    
    printf("================\n");
    dat = str_to_int_arr(num, cnt);
    gen_phone_words(dat, cnt);

    delete [] dat;
    return 0;

}

JavaScript

(function(){ alert(getMnemonics("867-5309")); })();


function getMnemonics(phoneNumber) {

  // we'll use a recursive method to grow our list of mnemonics
  // the list will need a seed, so we'll start with a = [""]
  //
  var a = [""], i;

  // we'll use a simple regex replace to get rid of any non-numeric input.
  // if we need to match to a dictionary of words, what do we do with
  // phone numbers that have "0"s or "1"s in them?
  //
  phoneNumber = phoneNumber.replace(/[^\d]/g,"");

  // we'll replace the current list with our new, larger list after each
  // iteration of the recursive function
  //
  for(i=0;i<phoneNumber.length;i++) a = addMnemonics(a,phoneNumber[i])

  // do we need to match to a hashset of words? if so, we'd consider our
  // array to be a list of possible answers. we'd need to iterate through
  // and add every possible answer to a new list of answers, only if the
  // possible answer exists in the hashset of words
  //
  return a;

}

function addMnemonics(a,s) {

  var b = {
    0: ["0"],
    1: ["1"],
    2: ["A","B","C"],
    3: ["D","E","F"],
    4: ["G","H","I"],
    5: ["J","K","L"],
    6: ["M","N","O"],
    7: ["P","Q","R"],
    8: ["S","T","U"],
    9: ["W","X","Y","Z"]
  }[s], c=[];

  // b is one of the arrays above, we'll return c = a x b

  for(i=0;i<a.length;i++) for(j=0;j<b.length;j++) c.push(a[i] + b[j]);
  return c;

}

Recursively try all possible characters for current digit (e.g. {a,b,c} for 2).

private static List<String> listWords(String num) {
    List<String> res = new ArrayList<>();
    gen(num, 0, new StringBuilder(), res);
    return res;
}

private static void gen(String num, int i, StringBuilder sb, List<String> res) {
    if (i >= num.length()) {
        res.add(sb.toString());
    } else {
        char ch = num.charAt(i);
        if (ch == '1') {
            sb.append(ch);
            gen(num, i + 1, sb, res);
            sb.delete(sb.length() - 1, sb.length());
        } else {
            char first = getFirst(ch);
            for (int j = 0; j < (ch == '7' || ch == '9' ? 4 : 3); j++) {
                char c = (char) (first + j);
                sb.append(c);
                gen(num, i + 1, sb, res);
                sb.delete(sb.length() - 1, sb.length());
            }
        }
    }
}

private static char getFirst(char ch) {
    switch (ch) {
        case '2':
            return 'a';
        case '3':
            return 'e';
        case '4':
            return 'g';
        case '5':
            return 'j';
        case '6':
            return 'm';
        case '7':
            return 'p';
        case '8':
            return 't';
        case '9':
            return 'w';
        default:
            throw new IllegalArgumentException();
    }
}

really?

for (i = 0; i >= 0; ) {
   if (a[i] != last char for n[i]) {
      a[i] = next char for n[i];
      if (++i >= n.length) {
          output a;
          --i;
      }
   }
   else {
      a[i--] = reset to nil;
   }
}

Use trie that would be easier and simple

where for w \in Wordset
convert it in number
insert Number(w) in trie