Given a seven-digit phone number, return all the character combinations that can be generated according to the following mapping:

Return the combinations in the lexicographical order.

Example

Input: “1234567”

Output: [

“adgjmp”,

“adgjmq”,

“adgjmr”,

“adgjms”,

“adgjnp”,

...

“cfilns”,

“cfilop”,

“cfiloq”,

“cfilor”,

“cfilos”]

First string “adgjmp” in the first line comes from the first characters mapped to digits 2,3,4,5,6 and 7 respectively. Since digit 1 maps to nothing, nothing is appended before 'a'. Similarly, the fifth string “adgjnp” generated from first characters of 2,3,4,5, second character of 6 and first character of 7. All combinations generated in such a way must be returned in the lexicographical order.

Notes

Input Parameters: The function has one parameter, a string of exactly seven digit characters.

Output: Return an array of the generated string combinations in the lexicographical order. If nothing can be generated, return an array with one string "-1".

Constraints:

● Input string is 7 characters long; each character is a digit.

Digits 0 and 1 map to nothing. Other digits map to either three or four different characters each.

Solution

Below are the solutions

‍

1) optimal_solution.java

This problem can be solved recursively. Consider the following function:

recurse (phoneNumber, result, digitMapping, currentIndex, word)

Here the parameters are:

● phoneNumber: Phone number given in the input of the problem

● result: An array of strings that will store all the generated combinations

● digitMapping: Hashmap of digits mapping to the corresponding characters

● currentIndex: The current index of the phone digit to be looped and the mappings to be added in the recursive function

● word: The current state of the word formed from previous digits before currentIndex

During recursion, if the currentIndex is equal to the length of the provided phoneNumber string, that means the recursive function has added a character for each digit and a valid combination is formed. This valid combination is added to the result array and the function is returned from there. This forms the base case for our recursive function.

If the mappings for all the digits have not been added, take the next digit from the phoneNumber using currentIndex. Find out all the mappings of that digit using digitMapping hashmap. Loop through all the characters for that digit, append it to the current word that has been formed and recurse for the next digit by incrementing currentIndex by 1. 

We are using a StringBuffer as the data type for word in the solution for performance reasons since strings are immutable in Java. We could use a character array or an equivalent to achieve the same performance goal.

Example. For the sake of simplicity, let us assume the phone number is 2 digits long and its value is input as "12". Let the mapping for this example be 

1 -> "a", "b"

2 -> "c", "d"

Note that this mapping is different from that given in the problem statement.

We initially call the recursion with recurse("12", [ ], digitMapping, 0, "")

Here, 12 is the input phoneNumber, next parameter holds the result initialized as empty array, next parameter contains the mapping for this example, next is currentIndex initialized as 0 and the last parameter is current state of word, initialized as empty string (or string builder, character array etc.)

Since the current index is not equal to the size of the phoneNumber, we loop for the mappings for "1" (the first digit of phoneNumber or phoneNumber[currentIndex]). So, in loop these two functions are called:

recurse("12", [ ], digitMapping, 1, "a") and 

recurse("12", [ ], digitMapping, 1, "b")

Similarly, for next iteration for digit 2, after looping these four functions are called:

recurse("12", [ ], digitMapping, 2, "ac") ,

recurse("12", [ ], digitMapping, 2, "ad") ,

recurse("12", [ ], digitMapping, 2, "bc") and

recurse("12", [ ], digitMapping, 2, "bd")

For all these functions, currentIndex is 2, which is the size of phoneNumber. So the word(s) sent during these calls are added to the result array and returned.

The recursive function in optimal_solution.java is called getWordsFromPhoneNumberUtil.

Since, as per the problem statement, digits 0 and 1 do not map to any characters, they have been removed before calling the recursive function as they won't contribute anything to the result array.

Time Complexity:

Since a digit can have a maximum of 4 mappings, we’ll make 4 recursive calls per digit at most. This recursion can go up to 7 levels deep. Worst case time complexity is therefore O(4^7).

Auxiliary Space Used:

For each function call, constant space is used in the call stack. Since we can have a maximum of 4^n functions in the stack, the auxiliary space used is O(4^n).

Space Complexity:

The space required to store the input string is of O(1).

The resultant list can have a maximum of 4^n elements, so total space complexity is:

O(1) (input) + O(4^n) (algorithm) + O(4^n) (output) = O(4^n)