本文共 1295 字，大约阅读时间需要 4 分钟。

深度搜索

class Solution:    def letterCombinations(self, digits: str) -> List[str]:        ans = []        if not digits:            return ans        phoneMap = {               "2": "abc",            "3": "def",            "4": "ghi",            "5": "jkl",            "6": "mno",            "7": "pqrs",            "8": "tuv",            "9": "wxyz",}        def backtrack(position, sub_res):            if len(sub_res) == len(digits):                ans.append("".join(sub_res[:]))                return            for i in range(position, len(digits)):                position = position + 1                for j in range(len(phoneMap[digits[i]])):                    sub_res.append(phoneMap[digits[i]][j])                    backtrack(position, sub_res)                    sub_res.pop()                # position = position - 1        backtrack(0, [])        return ans

广度搜索

class Solution:    def letterCombinations(self, digits: str) -> List[str]:        if not digits: return []        phone = ['abc','def','ghi','jkl','mno','pqrs','tuv','wxyz']        queue = ['']  # 初始化队列        for digit in digits:            for _ in range(len(queue)):                tmp = queue.pop(0)                for letter in phone[int(digit)-2]:                    queue.append(tmp + letter)        return queue