[DSA][Backtracking] Letter Combinations of a Phone Number

Leetcode 17

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.

**[What can I ask?]

• **Can the input digits be given? NO

**[Key Idea]

• **Extend the combinations by appending the letters corresponding to the next digit to the strings generated so far.

[Solution 1] Backtracking

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

        def backtrack(i, curStr):
            if len(curStr) == len(digits):
                res.append(curStr)
                return
            for c in digitToChar[digits[i]]:
                backtrack(i + 1, curStr + c)

        if digits:
            backtrack(0, "")

        return res

This problem requires generating all possible string combinations by choosing one letter for each digit in ‘digits’.

The key question is how to extend the combinations by appending the letters of the next digit to the strings generated so far. There are two main ways to implement this: backtracking (DFS) and iteration (BFS).

In the backtracking approach, we start from the first digit in ‘digits’ and select one of the letters mapped to that digit to add to the current string. We then move on to the next digit and recursively repeat the same process.

When the length of the current string matches the length of ‘digits’, it is added as a complete combination to the result. After the recursive call finishes, we revert to the previous state (backtrack) and try the next letter, exploring all possible combinations.

[Solution 2] Iteration

class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
        if not digits:
            return []

        res = [""]
        digitToChar = {
            "2": "abc",
            "3": "def",
            "4": "ghi",
            "5": "jkl",
            "6": "mno",
            "7": "qprs",
            "8": "tuv",
            "9": "wxyz",
        }

        for digit in digits:
            tmp = []
            for curStr in res:
                for c in digitToChar[digit]:
                    tmp.append(curStr + c)
            res = tmp
        return res

It is also possible to implement this problem without recursion, using only iteration. In this approach, at each step, a new array is created to extend the current combinations.

Starting with ‘res = [“”]’ represents the initial state where no letters have been chosen yet. Then, for each digit in ‘digits’ in order, all strings in ‘res’ are combined with every letter mapped to that digit to form new strings.

The newly generated strings are collected in a temporary array ‘tmp’, and ‘res’ is updated to ‘tmp’, which allows us to manage the combinations without mixing strings from previous and current steps. By extending each step sequentially in this way, all possible combinations can be generated without recursion or backtracking.

⏱️ Time Complexity If the length of digits is n, each digit can map to up to 4 letters, so the total number of possible combinations is 4ⁿ. Creating each combination requires copying a string of length n, so generating a single combination takes O(n) time. Therefore, the overall time complexity is O(n × 4ⁿ).

🧠 Space Complexity The final result array contains 4ⁿ strings, each of length n, so the space complexity is also O(n × 4ⁿ).