[Leetcode] 17. Letter Combinations of a Phone Number

Solution 1. product

from itertools import product

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

        values = [phone[d] for d in digits]
        comb = [''.join(val) for val in product(*values)]
        return comb if len(comb) != 1 else []

Solution 2. BFS

class Solution:
    def letterCombinations(self, n: str) -> List[str]:
        if n == '':
            return []

        options = ["", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"]

        queue = deque([""])

        for digit in n:
            digit = int(digit)

            for _ in range(len(queue)):
                curr = queue.popleft()
                for letter in options[digit]:
                    queue.append(curr + letter)

        return queue

Solution 3. Backtracking

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

        result = set()

        def backtrack(index, chosen):
            if index >= len(digits):
                if chosen:
                    result.add(chosen)
                return
            for s in phone[digits[index]]:
                backtrack(index+1, chosen + s)

        backtrack(0, "")

        return sorted(result)