Letter Combinations of a Phone Number

Problem Id: 17 Difficulty: Medium Tag: String Tag: Backtracking Tag: Depth-first search Tag: Recursion


Intuition

Simply use a DFS to get all combinations.

Solution


class Solution:
    MAPPING = [
        "",
        "",
        "abc",
        "def",
        "ghi",
        "jkl",
        "mno",
        "pqrs",
        "tuv",
        "wxyz"
    ]
    def letterCombinations(self, digits: str) -> List[str]:
        return [r for r in self._dfs(digits, 0) if r]

    def _dfs(self, digits, i):
        if i == len(digits):
            return [""]

        res = []
        children = self._dfs(digits, i + 1)
        for current in self.MAPPING[int(digits[i])]:
            for child in children:
                res.append(current + child)
        return res