Possible Words From A Phone Number
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.

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”}.

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

Question

Possible Words From A Phone Number

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”}.

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.

Accepted Answer

Step 1 : Explained the brute force approach of checking all possible n digit number and incrementing a counter when it satisfies our condition.
Step 2 : Time complexity was exponential so interviewer asked to optimize it.
Step 3 : Came up with a recursive approach and told the recursive relation.
Step 4 : To further optimize, memorized the approach using 2-d DP and explained to interviewer.
Step 5 : Interviewer was satisfied so proceeded with it, and wrote the code, dry ran on a test case.

Recursive relation:
dp[digit][n] = sum( dp[digit][n-1] + dp[digit-1][n-1] ... dp[0][n-1] )
where "digit" is the digit it is ending with in an n digit number.

Accepted Answer

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:

Create an empty array of strings to store the result. Let’s call it res.
Create a HashMap let’s say mp, to store the corresponding letters that map to the digits in T9 Keypad.
Create an empty string let’s say curr and an index variable, which is initialized to 0.
Call the backtrack function as possibleWordsUtil(S, res, curr, index, mp).
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):

If index == S.length, then add curr string to the res array and return.
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.

Space Complexity: OtherExplanation:

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)).

Time Complexity: OtherExplanation:

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)).