Letter Combinations of a Phone Number — LeetCode 17 Python Solution

The problem

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.

Example

Input

digits = "23"

Output

["ad","ae","af","bd","be","bf","cd","ce","cf"]

Python solution

class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
        if not digits:
            return []
        d = ["abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"]
        ans = [""]
        for i in digits:
            s = d[int(i) - 2]
            ans = [a + b for a in ans for b in s]
        return ans

Complexity

Pattern: Backtracking

Build candidates one choice at a time and abandon a branch the moment it cannot work. LeetCode 17. Letter Combinations of a Phone Number is filed here because LeetCode tags it Backtracking, which is the vocabulary this hub collects.

The backtracking guide has the Python template for the pattern and the 105 LeetCode problems that use it.

Related problems