Today is somewhat colder than yesterday in the Twin Cities of Minneapolis and St. Paul. It seems that we weekend will be quite a bit warmer than the rest of the week. This Sunday is Easter. It should be a nice day if you celebrate the holiday.
Earlier my wife went to get her hair done. Last week she got it cut for the first time since the COVID-19 pandemic started. It is amazing how the past year or so have gone by.
Today I picked another problem from LeetCode. I selected LeetCode 17 named Letter Combinations of a Phone Number. I am picking one problem per category from a list generated by LeetCode.
Given a string containing digits from 2-9 inclusive, return all possible letter combinations that the number could represent. Return the answer in any order. A mapping of digit to letters (just like on the telephone buttons) is given below. Note that 1 does not map to any letters. Constraints: o 0 <= digits.length <= 4 o digits[i] is a digit in the range ['2', '9'].
If interested please visit the LeetCode site and get the requirements from there. Not sure if problems change somewhat with time.
We are given a string of digits. Each digit is mapped to a string of characters. The idea is to generate all possible permutations for the specified digits.
We will solve the problem using the Java programming language, using the VSCode IDE on a Windows 10 computer. The signature for the method in question follows:
class Solution {
public List<String> letterCombinations(String digits) {
}
}
In addition I will solve the problem in my computer so I will not use the IDE provided by LeetCode. The simplest thing is to solve the problem on-line so you do not need to generate a test scaffold to receive the input data, call the method in question and display results.
23 main <<< digits ==>23<== main <<< lst: [ad, ae, af, bd, be, bf, cd, ce, cf] main <<< lst: [ad, ae, af, bd, be, bf, cd, ce, cf] main <<< digits ==><== main <<< lst: [] main <<< lst: [] 2 main <<< digits ==>2<== main <<< lst: [a, b, c] main <<< lst: [a, b, c]
The first line contains the digits we are given. The three examples were provided by LeetCode.
Our test scaffold reads the input line and displays it to make sure all is well so far.
It seems that we have two attempts to solve the problem. Both generate the same solution. That said; one is faster than the other.
I generated the faster version first. I then tried a recursive approach. It turned out slower than the first.
Please take a few moments to read the requirements and figure out an approach. I will wait…
…Now that you are back I would like to share my initial idea. It seems that each digit is mapped to a different string of letters. Numbers 0 and 1 are not mapped to letters. The rest of the digits are mapped to three or four letters.
The idea would be to take the first letter of the first digit and then go to the next digit and combine all letters. In other words for the first test case we will need to generate al the two letter combinations that we can with the letters associated with the digits “23”.
Note that other two examples deal with end cases. The first occurs when we were not provided a digit. The other when we are only provided a single digit.
This is a good time to think about these conditions. I will wait for as long as you need me to do so…
…OK, let’s continue by looking at the test scaffold. As I previously mentioned you do not need to implement this code. LeetCode provides a test scaffold.
/**
* Test scaffold.
*
* @throws IOException
*/
public static void main(String[] args) throws IOException {
// **** open buffered reader ****
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
// **** read digits ****
String digits = br.readLine().trim();
// **** close buffered reader ****
br.close();
// ???? ????
System.out.println("main <<< digits ==>" + digits + "<==");
// **** slower attempt ****
List<String> lst = letterCombinations2(digits);
// ???? ????
System.out.println("main <<< lst: " + lst.toString());
// **** faster attempt ****
lst = letterCombinations(digits);
// ???? ????
System.out.println("main <<< lst: " + lst.toString());
}
The code is quite simple. We collect the input and display it. We then invoke two implementations of the solution and display their associated results.
/**
* Entry call for recursion.
*
* Runtime: 4 ms, faster than 43.83% of Java online submissions.
* Memory Usage: 39.1 MB, less than 44.05% of Java online submissions.
*/
static List<String> letterCombinations2(String digits) {
// **** initialization ****
List<String> result = new ArrayList<String>();
// **** sanity ckeck(s) ****
if (digits == null || digits.length() == 0)
return result;
// **** ****
String[] digitToLetters = {
"",
"",
"abc",
"def",
"ghi",
"jkl",
"mno",
"pqrs",
"tuv",
"wxyz"
};
// **** recursive call ****
letterCombinations2(result, digits, "", 0, digitToLetters);
// **** return result ****
return result;
}
This is the recursive approach. We start by defining a list in which we will return all the combinations. Each combination will be represented by a string. If we are not provided digits, then we return an empty array list. This takes care of one of the test cases.
The digitToLetters String[] array holds the associated string of letter per digit. Note that digit 0 and 1 do not have letters associated with them.
We then call a recursive call which will collect all the combinations in the results array list. When done, we will return the results array list.
We are passing five arguments. We already discussed the first one. The second argument is the string holding the digits that we are given. In the first example the digits string holds “23”. The third argument represents a combination. At this point we pass an empty string since we do not have a valid combination yet. The fourth argument is the index to the digit we are processing in the digits string. We start with digit 0. Finally we pass the array that maps digits to strings of letters associated with each number.
/**
* Recursive call.
*/
static void letterCombinations2( List<String> result,
String digits,
String current,
int ndx,
String[] digitToLetters) {
// **** base call ****
if (ndx >= digits.length()) {
// **** add combination string to result ****
result.add(current);
// **** done ****
return;
}
// **** get string for this digit ****
String letters = digitToLetters[digits.charAt(ndx) - '0'];
// **** ****
for (int i = 0; i < letters.length(); i++) {
letterCombinations2(result, digits, current + letters.charAt(i),
ndx + 1, digitToLetters);
}
}
This recursive call is used to generate each and all combinations. In the base case, when the index reaches the end of the string, it signals that we have a current combination. We add it to the result and return. Note that when we are given a string of two digits the combinations have two characters. If we are given a string of one character we have combinations of a single character. Instead of checking the value of the index we could have checked the length of the current string.
We get the letters associated with the first digit.
We then enter a loop traversing all the letters associated with the first digit. For each letter we recursively call the method.
After the method returns we can extract the result array list and return it with all the combinations.
/**
* Combine two lists.
*
* Runtime: 1 ms, faster than 75.13% of Java online submissions.
* Memory Usage: 37.5 MB, less than 94.65% of Java online submissions.
*/
static List<String> letterCombinations(String digits) {
// **** sanity checks ****
if (digits == null || digits.length() == 0)
return new ArrayList<String>();
// **** initialization ****
List<String> lst = digitToCharList(digits.charAt(0));
// **** loop generating combinations ****
for (int i = 1; i < digits.length(); i++) {
lst = combine1(lst, digitToCharList(digits.charAt(i)));
}
// **** return list ****
return lst;
}
We start the second approach by performing some sanity checks.
The initialization step involves populating in the array list the letters associated with the first digit.
We then loop one per additional digit. At each pass of the loop we update the array list with the next set of combinations generated by the combine1() method. When done we return the array list.
/**
* Auxiliary method.
*
* Returns a list of characters associated with the
* specified digit.
*/
static List<String> digitToCharList(char digit) {
if (digit == '2')
return Arrays.asList("a", "b", "c");
else if (digit == '3')
return Arrays.asList("d", "e", "f");
else if (digit == '4')
return Arrays.asList("g", "h", "i");
else if (digit == '5')
return Arrays.asList("j", "k", "l");
else if (digit == '6')
return Arrays.asList("m", "n", "o");
else if (digit == '7')
return Arrays.asList("p", "q", "r", "s");
else if (digit == '8')
return Arrays.asList("t", "u", "v");
else
return Arrays.asList("w", "x", "y", "z");
}
This is the helper method that for each digit returns a list array with the letters associated with the specified digit.
/**
* Given two lists generate all combinations.
*/
static List<String> combine1(List<String> lst1, List<String> lst2) {
// **** initialization ****
List<String> lst = new ArrayList<String>();
// **** traverse the first list ****
for (int i = 0; i < lst1.size(); i++) {
// **** get next letter ****
String str = lst1.get(i);
// **** traverse the second list ****
for (int j = 0; j < lst2.size(); j++) {
lst.add(str + lst2.get(j));
}
}
// **** return the array list ****
return lst;
}
We initialize and array list which will hold a pass for all the combinations associated with the second list of letters.
The outer loop gets the string of combinations we have already generated.
The inner loop appends the letters from the second list.
When we are done, we return a list with all the combinations depending on the number of the digit.
Please feel free to add a statement at the end of the inner loop to see how the combinations are generated. It also helps trying longer digit strings.
Hope you enjoyed solving this problem as much as I did. The entire code for this project can be found in my GitHub repository.
If you have comments or questions regarding this, or any other post in this blog, please do not hesitate and leave me a note below. I will reply as soon as possible.
Keep on reading and experimenting. It is one of the best ways to learn, become proficient, refresh your knowledge and enhance your developer toolset.
One last thing, many thanks to all subscribers to this blog!!!
Regards;
John