Letter Combinations of a Phone Number

Problem Statement

Given a digit string, return all possible letter combinations that the number could represent. A mapping of digits to letters (just like on the telephone buttons) is given below.

The digit 0 maps to 0 itself.
The digit 1 maps to 1 itself.

Examples:
Input: Digit = “23”
Output: [“ad”, “ae”, “af”, “bd”, “be”, “bf”, “cd”, “ce”, “cf”].
Explanation:   The list shows the different possible combinations of the strings possible.

• “ad” – Press digit 2 once, digit 3 once.
• “ae”-   Press digit 2 once, digit 3 twice
• “af” –  Press digit 2 twice, digit 3 once, and so on.

Input:   Digit = “2”
Output: [“a”, “b”, “c”]

Approach: Backtracking

The problem can be solved using the backtracking approach. The idea is to consider a digit as the starting point and generate all possible combinations with that letter. Check the below illustration for a better understanding.

Algorithm

• If the input is empty, simply return an empty array.
• Initialize a hashmap that maps digits to their letters, i.e. mapping “2” to “a”, “b”, and “c”.
• Consider a backtracking function for generating all possible combinations:
  • Consider the parameters of the backtracking function as the path, i.e the current path we are traversing on and the index, i.e. on the digit we are on.
  • The base case would be, if our current combination of letters is the same length as the input digits, that iteration is complete. Therefore, insert it into the answer list, and backtrack.
  • Else, find all the possible combinations of letters that correspond with the current digit i.e. digits[index].
  • Traverse through the letters. For each letter, insert the letter to our current path, and backtrack again, and increment the index by 1.
  • Remove the letter from the path once the iteration is completed.

C++ Code

class Solution {
  public:
    vector < string > letterCombinations(string digits) {
      if (!digits.size()) {
        return {};
      }
 
      vector < string > combs;
      const vector < string > chars = {
        "0",
        "1",
        "abc",
        "def",
        "ghi",
        "jkl",
        "mno",
        "pqrs",
        "tuv",
        "wxyz"
      };
      string builder;
      build(builder, 0, digits, chars, combs);
      return combs;
    }
  void build(string builder, int i,
    const string & digits,
      const vector < string > & chars, vector < string > & combs) {
    if (i == digits.size()) {
      combs.push_back(builder);
      return;
    }
 
    int d = digits[i] - '0';
    for (char ch: chars[d]) {
      build(builder + ch, i + 1, digits, chars, combs);
    }
  }
};

Java Code

class Solution {
  private List < String > combinations = new ArrayList < > ();
  private Map < Character, String > letters = Map.of(
    '2', "abc", '3', "def", '4', "ghi", '5', "jkl",
    '6', "mno", '7', "pqrs", '8', "tuv", '9', "wxyz");
  private String phoneDigits;
 
  public List < String > letterCombinations(String digits) {
    if (digits.length() == 0) {
      return combinations;
    }
    phoneDigits = digits;
    backtrack(0, new StringBuilder());
    return combinations;
  }
 
  private void backtrack(int index, StringBuilder path) {
    if (path.length() == phoneDigits.length()) {
      combinations.add(path.toString());
      return;
    }
    String possibleLetters = letters.get(phoneDigits.charAt(index));
    for (char letter: possibleLetters.toCharArray()) {
      path.append(letter);
      backtrack(index + 1, path);
      path.deleteCharAt(path.length() - 1);
    }
  }
}

Python Code

class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
        if len(digits) == 0:
            return []
 
        letters = {
            "2": "abc",
            "3": "def",
            "4": "ghi",
            "5": "jkl",
            "6": "mno",
            "7": "pqrs",
            "8": "tuv",
            "9": "wxyz",
        }
 
        def backtrack(index, path):
            if len(path) == len(digits):
                combinations.append("".join(path))
                return
 
            possible_letters = letters[digits[index]]
            for letter in possible_letters:
 
                path.append(letter)
 
                backtrack(index + 1, path)
 
                path.pop()
 
        combinations = []
        backtrack(0, [])
        return combinations

Time Complexity: O(4^N * N), where N is the length of a digit string
Space Complexity: O(N)

Practice Problem – Letter Phone

FAQs

Q. How does the backtracking function work?
A. The backtracking approach is to consider a digit as the starting point and generate all possible combinations with that letter. The base case would be, if our current combination of letters is the same length as the input digits, that iteration is complete. Therefore, insert it into the answer list, and backtrack. Else, find all the possible combinations of letters that correspond with the current digit i.e. digits[index].

Q. What is the time complexity and space complexity of the backtracking approach?
A. The time complexity of the backtracking approach is O(4^N * N) and space complexity is O(N).