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