LC 17 - Letter Combinations of a Phone Number

Question

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 digits to letters (just like on the telephone buttons) is given below. Note that 1 does not map to any letters.

Example 1:

Input: digits = "23"
Output: ["ad","ae","af","bd","be","bf","cd","ce","cf"]

Example 2:

Input: digits = ""
Output: []

Example 3:

Input: digits = "2"
Output: ["a","b","c"]

Constraints:

• 0 <= digits.length <= 4
• digits[i] is a digit in the range ['2', '9'].

Links

Question here and solution here

Solution

concept

Use backtracking to solve the problem. In the for loop we iterate through all digits at the present level (i.e. current digit), when it backtrack, it will consider other combination at the same levels (i.e. if 2,3,4, it will consider [a,d,g] then go to [a,d,h],[a,d,i], and then [a,e,g], then go to [a,e,h], [a,e,i] ).

code

class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
        d_to_c = {
            "2": ["a", "b", "c"],
            "3": ["d", "e", "f"],
            "4": ["g", "h", "i"],
            "5": ["j", "k", "l"],
            "6": ["m", "n", "o"],
            "7": ["p", "q", "r", "s"],
            "8": ["t", "u", "v"],
            "9": ["w", "x", "y", "z"]
            }
        ans = []
        curr = []

        def dfs(idx):
            if idx >= len(digits):
                tmp = curr.copy()
                ans.append("".join(tmp))
                return
            for c in d_to_c[digits[idx]]:
                curr.append(c)
                dfs(idx + 1)
                curr.pop()
        dfs(0)
        return ans if digits else []

Complexity

time: $O(n * 4^n)$
space: $O(n)$