Letter Combinations of a Phone Number

The problem description can be found in LeetCode.

Approach

As usual, picturing a possible input is always a great choice.

In particular, assuming that we have an input like 23, we would need to combine the strings abc for 2 and def for 3, respectively.

So, we could start by picking a first and combine it with every letter in def. Then, we could do the same with b and then c.

This would require looping to every character and then build the result during the iteration itself. However, here we do not know how many characters we can have. So, we cannot simply loop over all possible characters with a simple chain of for loops.

For this reason, let's try to draw the space tree of this problem.

As you can see, every leaf node would contain a piece of our solution. We could simply concatenate the characters along that path to build it.

Besides adding characters along the path, we can also remove them once we explore them, hence applying a Backtracking approach.

Solution

from typing import List


class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
        def dfs(i: int, curr: List[str], combs: List[str]) -> None:
            if i == len(digits):
                if curr:
                    combs.append("".join(curr))
            else:
                for letter in mapping[digits[i]]:
                    curr.append(letter)
                    dfs(i + 1, curr, combs)
                    curr.pop()

        mapping = {
            "2": "abc",
            "3": "def",
            "4": "ghi",
            "5": "jkl",
            "6": "mno",
            "7": "pqrs",
            "8": "tuv",
            "9": "wxyz",
        }
        ans: List[str] = []

        dfs(0, [], ans)
        return ans

Complexity

• Time: $O(m^{n}n)$
• Space: $O(n)$

Where $n$ is the size of the digits list and $m$ is the maximum size of characters that a digit might have. In this case, $m=4$.