算法 17 电话号码字母组合 - 图1

    1. # 给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。 
    2. # 
    3. #  给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。 
    4. # 
    5. #  
    6. # 
    7. #  示例: 
    8. # 
    9. #  输入："23"
    10. # 输出：["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].
    11. #  
    12. # 
    13. #  说明: 
    14. # 尽管上面的答案是按字典序排列的，但是你可以任意选择答案输出的顺序。 
    15. #  Related Topics 深度优先搜索 递归 字符串 回溯算法 
    16. #  👍 1061 👎 0
    19. # leetcode submit region begin(Prohibit modification and deletion)
    20. class Solution(object):
    21.     def letterCombinations(self, digits):
    22.         """
    23.         :type digits: str
    24.         :rtype: List[str]
    25.         """
    26.         phoneMap = {
    27.             "2": "abc",
    28.             "3": "def",
    29.             "4": "ghi",
    30.             "5": "jkl",
    31.             "6": "mno",
    32.             "7": "pqrs",
    33.             "8": "tuv",
    34.             "9": "wxyz",
    35.         }
    36.         if not digits:
    37.             return []
    39.         collection = []
    40.         res = []
    42.         def backTrace(index):
    43.             if index == len(digits):
    44.                 res.append("".join(collection))
    45.             else:
    46.                 digit = digits[index]
    47.                 if digit in phoneMap:
    48.                     for c in phoneMap[digit]:
    49.                         collection.append(c)
    50.                         backTrace(index + 1)
    51.                         collection.pop()
    53.         backTrace(0)
    55.         return res
    58. # leetcode submit region end(Prohibit modification and deletion)
    59. print(Solution().letterCombinations("23"))