Possible Words From A Phone Number

Hard
0/120
Average time to solve is 55m
profile
Contributed by
21 upvotes
Asked in companies
MicrosoftFacebookExpedia Group

Problem statement

After years of research, Ninja is finally able to invent the time machine, and now he is back to the good old days when T9 keypads were being used in mobile phones.

Being a curious person, Ninja wants to find out all possible strings that can be formed by pressing the keys of the phone.

Formally, you are given a string S, that consists of digits from 2-9 (both inclusive), your task is to find out all the possible strings that can be formed from the input string by mapping the digits to the letters as in a T9 keypad. Then, print the strings in a lexicographically sorted order.

T9_Keypad

For Example: 
If S = “34”, then all the possible letters that can be formed from string S are {“dg”, “dh”, “di”, “eg”, “eh”, “ei”, “fg”, “fh”, “fi”}.
Detailed explanation ( Input/output format, Notes, Images )
Input format: 
The first line contains an integer 'T' which denotes the number of test cases or queries to be run. Then, the 'T' test cases follow.

The first line of each test case contains a string S.
Output format: 
For each test case, print all the possible strings separated by a single space in lexicographically sorted order, that can be formed from the input string by mapping the digits to the letters as in a T9 keypad.

The output of each test case will be printed in a separate line.
Note: 
You do not need to print anything, it has already been taken care of. Just implement the given function.
Constraints: 
1 <= T <= 10
1 <= |S| <= 7
where |S| denotes the length of the string S.

Time limit: 1 sec.
Sample Input 1:
1
5
Sample Output 1:
j k l
Explanation for sample 1:
For the first test case, the words that can be formed from the string S are {“j”, “k”, “l”}.
Sample Input 2:
2
37
79
Sample Output 2:
dp dq dr ds ep eq er es fp fq fr fs
pw px py pz qw qx qy qz rw rx ry rz sw sx sy sz
Explanation for sample 2:
For the first test case, the words that can be formed from the string S are  {“dp”, “dq”, “dr”, “ds”, “ep”, “eq”, “er”, “es”, “fp”, “fq”, “fr”, “fs”}.

For the second test case, the words that can be formed from the string S is are {“pw”, “px”, “py”, “pz”, “qw”, “qx”, “qy”, “qz”, “rw”, “rx”, “ry”, “rz”, “sw”, “sx”, “sy”, “sz”}.
Hint

Think of a solution using backtracking.

Approaches (1)
Backtracking

Approach:

The idea is to use a backtracking algorithm. So, we traverse each digit of the string S, we have 3 options to choose if the digit belongs to {2,3,4,5,6,8} or 4 options if it belongs to {7,9}. So, go through all possible options and add a letter in the keypad that map to the current digit and add it to the current string. If there are no more digits to be checked, then add this string to the result array.

Steps:

  1. Create an empty array of strings to store the result. Let’s call it res.
  2. Create a HashMap let’s say mp, to store the corresponding letters that map to the digits in T9 Keypad.
  3. Create an empty string let’s say curr and an index variable, which is initialized to 0.
  4. Call the backtrack function as possibleWordsUtil(S, res, curr, index, mp).
  5. Finally, return the res array. Note that this method always results in the strings being lexicographically sorted, so we do not need to sort the res array separately.

void possibleWordsUtil(S, res, curr, index, mp):

  1. If index == S.length, then add curr string to the res array and return.
  2. Run a loop i = 0 to mp[S[index]].size() and do:
    1. Add mp[S[index]][i] to the curr string.
    2. Call the backtrack function recursively by increasing the index by 1, i.e. possibleWordsUtil(S, res, curr, index+1, mp).
    3. Remove the last element from the curr string.
Time Complexity

O((N + M) * (3 ^ N * 4 ^ M)), where ‘N’ denotes the number of digits in the string ‘S’, that maps to 3 letters such as {2, 3, 4, 5, 6, 8} and ‘M’ denotes the number of digits in the string ‘S’, that maps to 4 letters such as {7, 9}.

 

In the worst case, a total number of (3 ^ N * 4 ^ M) strings can be formed and each string has the length in the order of N + M. Hence, the overall time complexity is O((N + M) * (3 ^ N * 4 ^ M)).

Space Complexity

O((N + M) * (3 ^ N * 4 ^ M)), where ‘N’ denotes the number of digits in the string ‘S’, that maps to 3 letters such as {2, 3, 4, 5, 6, 8} and ‘M’ denotes the number of digits in the string ‘S’, that maps to 4 letters such as {7, 9}.

 

In the worst case, a total number of (3 ^ N * 4 ^ M) strings can be formed and each string has the length in the order of N + M. We have to keep all these strings in a result array. Hence, the overall space complexity is O((N + M) * (3 ^ N * 4 ^ M)).

Code Solution
(100% EXP penalty)
Possible Words From A Phone Number
Full screen
Console