CareerCup

Generate all possible combination of strings.
If the dictionary is available in the form of a trie, then we can traverse down the trie multiple times along the seq of numbers pressed assuming that the trie has a marker for end of word for every complete word, if the word is identified print it.

Below I am producing the code that generates any length of words based on the given conversion map (number to possible characters). Though filtering out all the meaningful words is not implemented (leaving this to make the code base as concise as possible), I think the main algorithm for generating the combinations (please note, this is not a permutation) of all the possible words is quite straightforward.

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

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 = NULL;

    if (argc > 1)
        num = argv[1];
    else
        num = "+37491210701";

    dat = str_to_int_arr(num, cnt);
    gen_phone_words(dat, cnt);

    delete [] dat;
    return 0;
}

Without any further explanation, this question looks like a permutation problem.

@Varsha : Can you explain the concept of meaningful word again?

Without any further explanation, this question looks like a permutation problem.

@Varsha : Can you explain the concept of meaningful word again?

Without any further explanation, this question looks like a permutation problem.

@Varsha : Can you explain the concept of meaningful word again?

Mine was similar question.

assumption : we have number in array format whose size is size_of_num, 2-D array is defined.

int size_of_num;

define_word(static int *num,static chat *var,static char **mat,int i)
{

for(j=0;j<3;j++)
{
var[i]=mat[num[i]][j];
define_word(num,var,mat,i+1);
if(i==size_of_num)
if(find_word_in_dictionary(var))
printf("%s\n",var);
}
}

private HashMap<Integer, char[]> map = new HashMap<Integer, char[]>();


public List<String> phoneBook(int []arg) {
int len = 0;
int count = 1;
for(int i = 0;i < arg.length; ++i) {
if (map.containsKey(arg[i])) {
len ++;
count *= map.get(arg[i]).length;
}
}
char[][] array = new char[count][len];
for(int i = 0; i < arg.length; ++i) {
if (!map.containsKey(arg[i]))
continue;
char[] el = map.get(arg[i]);
count /= el.length;
int start = 0;
for(int j = 0; j < el.length; ++j) {
for(int k = 0; k < count; ++k) {
array[start++][i] = el[j];
}
}
}
List<String> strList = new LinkedList<String>();
for(int i = 0; i < array.length; ++i) {
strList.add(new String(array[i]));
}
return strList;
}

We can also simulate this problem into Graph, Where its Vertices are the dial Number(2,3,4,....9) and edges are{{2 -> A,B,C}, {3 ->D,E,F}.........}
and using the traversing Techniques it can print all possible permutation.

if m wrong plz give any suggestions