leetcode | 17.电话号码的字母组合

17.电话号码的字母组合

题目描述

给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。
给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。

题目链接

思路

1.遍历并组合每一个数字对应的字母列表 –> letterCombinations()
点击这里查看完整解题思路！！！
2.使用内置库 –> letterCombinations1()
3.回溯 –> letterCombinations2()
回溯法和使用内置库思路见leetcode题解

代码

class Solution:
    num2ch = {
        '2': ['a', 'b', 'c'],
        '3': ['d', 'e', 'f'],
        '4': ['g', 'h', 'i'],
        '5': ['j', 'k', 'l'],
        '6': ['m', 'n', 'o'],
        '7': ['p', 'q', 'r', 's'],
        '8': ['t', 'u', 'v'],
        '9': ['w', 'x', 'y', 'z']
    }

    def letterCombinations(self, digits: str) -> list:
        if len(digits) == 0:
            return []

        list1 = []  # 用于存储digits数组中每个字符对应的字母列表
        for d in digits:
            list1.append(self.num2ch[d])

        i = 0
        j = 1
        while j < len(list1):
            list1[j] = self.concat(list1[i], list1[j])
            i = j
            j += 1

        return list1[-1]

    def concat(self, list1, list2):
        res = []
        for e1 in list1:
            for e2 in list2:
                res.append(e1 + e2)
        return res

    def letterCombinations1(self, digits: str):
        if not digits:
            return list()

        phoneMap = {
            "2": "abc",
            "3": "def",
            "4": "ghi",
            "5": "jkl",
            "6": "mno",
            "7": "pqrs",
            "8": "tuv",
            "9": "wxyz",
        }

        groups = (phoneMap[digit] for digit in digits)

        import itertools
        return ["".join(combination) for combination in itertools.product(*groups)]

    def letterCombinations2(self, digits: str):
        if not digits:
            return list()

        phoneMap = {
            "2": "abc",
            "3": "def",
            "4": "ghi",
            "5": "jkl",
            "6": "mno",
            "7": "pqrs",
            "8": "tuv",
            "9": "wxyz",
        }

        def backtrack(index: int):
            if index == len(digits):
                combinations.append(''.join(combination))
            else:
                digit = digits[index]
                for letter in phoneMap[digit]:
                    combination.append(letter)
                    backtrack(index + 1)
                    combination.pop()

        combination = list()
        combinations = list()
        backtrack(0)
        return combinations


if __name__ == '__main__':
    slt = Solution()
    digits = "23"
    res = slt.letterCombinations2(digits)
    print(res)