Letter Combinations of a Phone Number

Problem Statement

You are given a string digits made up of digits from 2 through 9 inclusive.

Each digit (not including 1) is mapped to a set of characters as shown below:

A digit could represent any one of the characters it maps to.

Return all possible letter combinations that digits could represent. You may return the answer in any order.

Example 1:

Input: digits = "34"
Output: ["dg","dh","di","eg","eh","ei","fg","fh","fi"]

Example 2:

Input: digits = ""
Output: []

Constraints:

  • 0 <= digits.length <= 4
  • 2 <= digits[i] <= 9

You should aim for a solution with O(n \cdot 4^n) time and O(n) space, where n is the length of the input string.

You should aim for a solution with O(n \cdot 4^n) time and O(n) space, where n is the length of the input string.

Hint 1

We can use a hash map to pair all the digits with their corresponding letters. Think of this as a decision tree, where at each step, we have a digit, and we select one of multiple characters to proceed to the next digit in the given string digits. Can you think of an algorithm to generate all combinations of strings?

Hint 2

We can use backtracking where we select a character and process it, then backtrack to process another character. We recursively iterate on the given string with index i. At each step, we consider the letters from the hash map that correspond to the digit at the i-th index. Can you think of the base condition to stop this recursive path?

Hint 3

We initialize an empty string that represents the choices of the characters throughout the current recursive path. When the index i reaches the end of the string, we add the current string to the result list and return.

Solution

Backtracking

def letter_combinations(digits: str) -> List[str]:
    digit_to_char = {
        "2": "abc",
        "3": "def",
        "4": "ghi",
        "5": "jkl",
        "6": "mno",
        "7": "qprs",
        "8": "tuv",
        "9": "wxyz",
    }
    res = []


    def backtrack(i, cur_str):
        if len(cur_str) == len(digits):
            res.append(cur_str)
            return
        for char in digit_to_char[digits[i]]:
            backtrack(i + 1, cur_str + char)


    if digits:
        backtrack(0, "")


    return res

Time complexity: O(n \cdot 4^n) Space complexity: O(n)