Letter Combinations of a Phone Number

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


Simply use a DFS to get all combinations.


class Solution:
    MAPPING = [
    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