# Possible Words From A Phone Number

Posted: 16 Jan, 2021

Difficulty: Hard

#### 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 <= T <= 10
1 <= |S| <= 7
where |S| denotes the length of the string S.
Time limit: 1 sec.
```

Approach 1

**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
**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:- Add
**mp[S[index]][i]**to the**curr**string. - Call the backtrack function recursively by increasing the
**index**by 1, i.e.**possibleWordsUtil(S, res, curr, index+1, mp)**. - Remove the last element from the
**curr**string.

- Add