Problem Statement in English

You’re 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.

Approach

We can solve this problem using a backtracking approach. The idea is to map each digit to its corresponding letters (as on a traditional phone keypad) and then generate all possible combinations of these letters based on the input digits.

For each recursive call, we’ll have 2 arguments: the current state of the combination being built (the string state) and the index of the digit we’re currently processing.

If we reach the end of the digits, we add the current combination to our answer list. Otherwise, we iterate through the letters corresponding to the current digit and make recursive calls for each letter.

And we’re done!

Solution in Python



class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
        if not digits:
            return []
        
        hm: dict[int, tuple] = {
            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 = []

        def dfs(state, index):
            if index >= len(digits):
                ans.append(state)
                return

            converted = int(digits[index])
            if converted in hm:
                for char in hm[converted]:
                    dfs(state + char, index + 1)
            else:
                dfs(state, index + 1)
            pass

        dfs("", 0)

        return ans

Complexity

  • Time: $O(4^n)$
    Since the maximum number of letters for a digit is 4 (for digits 7 and 9), and we are generating combinations for each digit, the time complexity is exponential in terms of the number of digits n.

  • Space: $O(4^n)$
    Since we are storing all possible combinations in the answer list, the space complexity is also exponential in terms of the number of digits n.

And we are done.