Solution: Letter Combinations of a Phone Number

Let's solve the Letter Combinations of a Phone Number problem using the Subsets pattern.

We'll cover the following

Statement

Given a string containing digits from 2 to 9 inclusive, with the possibility of each digit appearing multiple times, return all possible letter combinations that the number could represent. Return the answer in any order.

The illustration below shows the mapping of digits to letters in a telephone dial pad.

Note: The number 11 on the telephone dial pad does not correspond to any letter, so the input string only contains digits from 22 to 99.

Constraints:

  • 0≤0 \leq digits.length ≤4\leq 4

  • digits[i] is a digit in the range [2,9][2, 9]

Pattern: Subsets

This problem lends itself naturally to the subsets pattern. To solve this problem, we can use a backtracking algorithm as the solution template to correctly generate all the possible combinations.

Solution

Since we need to explore different choices for each digit and generate valid combinations, we can use the subset technique with backtracking. It involves iterating through each digit in the input sequence, recursively generating combinations of letters corresponding to that digit. Each recursive step explores all possible letters for the current digit, appending each letter to the current combination and moving to the next digit. If the combination reaches the same length as the input sequence, it is added to the list of valid combinations. However, if a certain combination doesn't match the expected length, we backtrack to the previous state and explore other options. This process continues until all digits have been processed.

For example, let’s consider the input digits “23”. We start with an empty combination list and the initial index of 0. For the first digit “2”, the corresponding letters are [“a”, “b”, “c”]. We add “a” to the combination and recursively call the function with the next index of 1. For the second digit “3”, the corresponding letters are [“d”, “e”, “f”]. We add “d” to the combination and recursively call the function with the next index of 2. At this point, the length of the combination is equal to the length of the input string, so we join the combination into a string, “ad”, and append it to the list of combinations. Then, we remove the last letter “d” from the combination and move on to the next letter, “e”, in the letters corresponding to digit “3”. We repeat this process until we have explored all possible combinations.

The algorithm works as follows:

  1. It first checks if the input string is empty. If it is empty, we will return an empty list immediately.

  2. Creates a hash map, digits_mapping, which maps each digit to a list of corresponding letters. For example, “2” corresponds to letters “a”, “b”, and “c”.

  3. The backtrack function is then called to generate the combinations recursively. It takes the parameters, index (the current index in the digits string), path (the current combination of letters being built), digits (the input string of digits), letters (the mapping of digits to letters) and combinations (a list to store the generated combinations). Within the backtrack function, we will perform the following steps:

    1. If the length of path is equal to the length of digits, it means we have a complete combination. The path is joined into a string and appended to the combinations list.

    2. Otherwise, the function retrieves the list of possible letters corresponding to the digit at the current index. It then iterates through each letter and performs the following steps:

      1. It adds the letter to the path.

      2. It recursively calls backtrack with the updated index and path to move on to the next digit.

      3. After the recursive call, the letter is removed from the path to backtrack and explore other letter combination possibilities.

  4. Finally, the combinations list is returned as a result that contains all possible letter combinations made from the numbers in the string.

The slides below help to understand the solution in a better way.

Press + to interact
canvasAnimation-image
1 of 22

Let’s look at the code for this solution below:

import java.util.*;
class LetterCombinations {
    // Use backtrack function to generate all possible combinations
    public void backtrack(int index, StringBuilder path, String digits, Map<Character, String[]> letters, List<String> combinations) {
        if (path.length() == digits.length()) {
            
            combinations.add(path.toString());
            return; 
        }
        
        char digit = digits.charAt(index);
        String[] possibleLetters = letters.get(digit);
        for (String letter : possibleLetters) {
            path.append(letter);
            backtrack(index + 1, path, digits, letters, combinations);
            path.deleteCharAt(path.length() - 1);
        }
    }
    
    public List<String> letterCombinations(String digits) {
        List<String> combinations = new ArrayList<>();
        if (digits.length() == 0) {
            return combinations;
        }
        Map<Character, String[]> digitsMapping = new HashMap<>();
        digitsMapping.put('1', new String[]{""});
        digitsMapping.put('2', new String[]{"a", "b", "c"});
        digitsMapping.put('3', new String[]{"d", "e", "f"});
        digitsMapping.put('4', new String[]{"g", "h", "i"});
        digitsMapping.put('5', new String[]{"j", "k", "l"});
        digitsMapping.put('6', new String[]{"m", "n", "o"});
        digitsMapping.put('7', new String[]{"p", "q", "r", "s"});
        digitsMapping.put('8', new String[]{"t", "u", "v"});
        digitsMapping.put('9', new String[]{"w", "x", "y", "z"});
        backtrack(0, new StringBuilder(), digits, digitsMapping, combinations);
        return combinations;
    }
    
    
    public static void main(String[] args){
       LetterCombinations sol = new LetterCombinations();
       String[] digitsArray = {"23", "73", "426", "78", "925", "2345"};
       for(int i = 0; i < digitsArray.length; i++){
          System.out.println((i + 1)+ ".\tAll letter combinations for  "+digitsArray[i]+ ": "+ sol.letterCombinations(digitsArray[i]));
          System.out.println(new String(new char[100]).replace('\0', '-'));
       }
    }
}
Letter Combinations of a Phone Number

Solution summary

To recap, the solution to this problem can be divided into the following parts:

  1. The backtracking approach used in the solution considers a digit as the starting point and generates all possible combinations with that letter.
  2. The base case for the backtracking function will be that if our current combination of letters has the same length as the input digits, the iteration is complete.
  3. Otherwise, we find all the possible combinations of letters that correspond with the current digit.

Time complexity

To make one combination for the given input string, each digit in the input string has kk possible options. Now, to generate all possible combinations for the given input string, all the kk options for each digit will be exhausted. For example, if we have two digits in the input string, then the total possible combinations for this string will be k×kk \times k, i.e., k2k^2. This implies that if we have nn digits in the input string, then there will be total knk^n combinations.

The cost to build one combination is nn because we append the characters one by one until we get a string of length nn (refer to line 16 of the code). Consequently, to build all the possible combinations (knk^n), it will take kn×nk^n \times n time.

As per the analysis above, the overall time complexity of this solution is kn×nk^n \times n .

Space complexity

The recursion goes as deep as the number of digits in the input string. For example, if the input is “234234”, the recursion will have a maximum depth of 33. So, if the input has nn digits, the maximum depth of the recursion stack is nn. At each level of recursion, the function maintains some local variables that take up constant space.

The primary factor contributing to the space complexity of this solution is the space used by the recursion stack. Because the recursion goes nn levels deep, and each level uses a constant amount of space, the total space used by the recursion stack is proportional to nn. Therefore, the space complexity of this solution is O(n)O(n).

Level up your interview prep. Join Educative to access 70+ hands-on prep courses.