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