New update is available. Click here to update.

Last Updated: 10 Mar, 2021

Hard

```
You can convert the list of valid words into any data structure you desire.
```

```
If the sequence of number = 2633, and the list of valid words = [ride, used, code, tree, boed],
Then you would print βcodeβ and βboedβ as they can be formed by using the digit sequence and they are also present in the list of valid words.
```

```
The first line contains an integer βTβ which denotes the number of test cases or queries to be run. Then the test cases are as follows.
The first and line of each test case consist of the sequence of numbers.
The second line of each test case consists of βWβ, which denotes the number of given valid words.
The third and final line of each test case consists of the list of βWβ valid words.
```

```
For each test case, print the list of words that can be formed using the given sequence of numbers and are also present in the given list of valid words.
Print the output of each test case in a separate line.
```

```
You donβt need to print anything; It has already been taken care of. You just need to complete the given function.
```

```
1 <= T <= 10
1 <= Sequence <= 10
1 <= W <= 200
where βTβ is the number of test cases, βsequenceβ is the length of the given sequence of numbers, and βWβ, is the number of valid words each test case can have.
Time limit: 1 sec
```

Approaches

This is the most basic approach and we will simply try every possible value for each digit in the sequence with all other possible values.

- We start by taking the first digit of the sequence and run through all the characters that map to that digit.
- For every character, we then add it to a variable letβs say βpreβ and recurse, by passing the βpreβ downwards.
- We do this until we run out of characters and then simply print the variable βpreβ that would by now contain the full word, if we can find it in the vector of valid words, meaning if it is a valid word.

**Algorithm:**

- We start by mapping the digits with their corresponding letters.
- For the main function, we start with creating a vector that will store our final βresultβ
- Create a recursive function with the base case:
- If there are no more digits to check, meaning if the length of the word is equal to the length of the sequence:
- Add the word βpreβ, which is the current word to the βresultβ vector

- For the main function, we get characters that match the given digit with the help of the precomputed mapping of digits with their corresponding letters.
- Recursively call for the rest of the digits until we reach the end of the sequence.
- Check for βpreβ in the list of valid words:
- If found:
- Push it into βresultβ.

- If found:

- If there are no more digits to check, meaning if the length of the word is equal to the length of the sequence:
- Finally, return the result vector.

In this approach, we will be doing a little bit of preprocessing in order to make the algorithm faster. So, instead of creating all the possible words from the given sequence and then checking them one by one in the list of valid words, we will simply generate the sequence of all the valid words and check them one by one if they match the given sequence of digits.

- Create a hashmap from (character -> integer) for all the characters from βaβ - βzβ.
- Iterate through every word and convert it into its corresponding numeric sequence. For example: βcodingβ will be computed as 263464.
- Compare this sequence with the given sequence:
- If both sequences are equal:
- Store it in the βresultβ vector.

- If not:
- Continue

- If both sequences are equal:
- On reaching the end of the valid words list, return the βresultβ vector.