Sunday, June 10, 2012

Print all possible combinations of strings that can be made using a keypad given a number


Consider a phone keypad where every number has few english alphabet characters associated with it. When a user types some numbers on screen , print all possible permutations of string possible using the characters associated with those numbers. Example: if 1 corresponds to A B C and 2 corresponds to DEF. Then number "12" might represent any of the following : AD, AE, AF, BD, BE, BF, CD, CE, CF.
The problem is very similar to this problem.
The key steps in writing an this function are:
  • Initialize a keypad array of strings with alphabets corresponding to each number.
  • Now one by one choose each of the characters corresponding to the number and recurse.
  • Make sure to keep a check for the digit 9 as it will have only 2 characters.
string keypad[9] = {"ABC", "DEF", "GHI", "JKL", "MNO", "PQR", "STU", "VWX", "YZ"};

void keys(char* num, char *s, int start, int end)
{
    if(start == end)
    {
        cout<<s<<endl;
        return;
    }
    
    s[start] = keypad[(num[start] - '0' - 1)][0];
    keys(num, s,start+1,end);
    s[start] = keypad[(num[start] - '0' - 1)][1];
    keys(num, s,start+1,end);
    if((num[start] - '0' - 1) < 8)
    {
        s[start] = keypad[(num[start] - '0' - 1)][2];
        keys(num, s,start+1,end);
    }
}

No comments:

Post a Comment