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

# @Time    : 2023/10/13 00:00
# @Author  : Lan
# @File    : 17. 电话号码的字母组合.py
# @Software: PyCharm
# @link    : https://leetcode.cn/problems/letter-combinations-of-a-phone-number/description/
"""
给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。
给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。
"""
from typing import List


class Solution:
    key_value = [
        "",
        "",
        "abc",
        "def",
        "ghi",
        "jkl",
        "nmo",
        "pqrs",
        "tuv",
        "wxyz"
    ]
    result = []
    temp = []

    def backtracking(self, digits, index):
        if index == len(digits):
            if self.temp:
                self.result.append(''.join(self.temp))
            return
        letters = self.key_value[int(digits[index])]
        for i in range(len(letters)):
            self.temp.append(letters[i])
            self.backtracking(digits, index + 1)
            self.temp.pop()

    def letterCombinations(self, digits: str) -> List[str]:
        self.result = []
        self.backtracking(digits, 0)
        return self.result


print(Solution().letterCombinations(''))