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

这道题可以使用回溯算法来解决。

从字符串的第一个数字开始，找到对应的字母，然后继续递归下一个数字。直到所有数字都被遍历完成，将当前的字母组合加入结果列表中。

具体实现如下：

class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
        if not digits:
            return []

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

        res = []

        def backtrack(combination, next_digits):
            if not next_digits:
                res.append(combination)
                return
            for letter in phone_map[next_digits[0]]:
                backtrack(combination + letter, next_digits[1:])

        backtrack("", digits)

        return res

时间复杂度为 $O(3^m \times 4^n)$，其中 $m$ 表示输入中对应三个字母的数字个数，$n$ 表示输入中对应四个字母的数字个数。