17. 电话号码的字母组合

Difficulty
Medium
Tags
回溯
URL
https://leetcode-cn.com/problems/letter-combinations-of-a-phone-number/
Star
给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。
给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。
notion imagenotion image
示例 1：
输入：digits = "23"
输出：["ad","ae","af","bd","be","bf","cd","ce","cf"]
示例 2：
输入：digits = ""
输出：[]
示例 3：
输入：digits = "2"
输出：["a","b","c"]
提示：
  • 0 <= digits.length <= 4
  • digits[i] 是范围 ['2', '9'] 的一个数字。

法1 回溯

思路
理解清楚层之间的关系。
理解清楚当前层的选择是由什么决定的，下一层的选择是由什么决定的。当前层的选择和下一层的选择之间的关系是什么。
画好树状的图
题解
class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
        self.KEY = {'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']}
        self.res = []
        if len(digits) == 0:
            return []
        self.backtrck(path=[], digits=digits, start=0)
        return self.res
    def backtrck(self, path, digits, start):
        if len(path) == len(digits):
            self.res.append(''.join(path))
            return
        if start >= len(digits):
            return
        chars = self.KEY[digits[start]]
        for i in chars:
            path.append(i)
            self.backtrck(path, digits, start+1) 
            path.pop()