17.电话号码的字母组合

backtracking, https://leetcode.cn/problems/letter-combinations-of-a-phone-number/

给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。

给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。

示例 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'] 的一个数字。

python

from typing import List
class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
        num_to_char = {'2':'abc','3':'def','4':'ghi','5':'jkl','6':'mno',
        '7':'pqrs','8':'tuv','9':'wxyz'}
        ans = []
        def backtrack(combination, next_digits):
            if len(next_digits) == 0:
                ans.append(combination)
            else:
                for letter in num_to_char[next_digits[0]]:
                    backtrack(combination+letter, next_digits[1:])

        if digits:
            backtrack("", digits) # start with an empty string
        return ans

if __name__ == "__main__":
    digits = "23"
    print(Solution().letterCombinations(digits))

上面代码中使用了隐式回溯，因为回溯函数 backtrack 的参数中直接传递了新的状态。

显示回溯代码如下：

python

from typing import List

class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
        num_to_char = {'2': 'abc', '3': 'def', '4': 'ghi', '5': 'jkl', '6': 'mno',
                       '7': 'pqrs', '8': 'tuv', '9': 'wxyz'}
        ans = []

        def backtrack(combination, next_digits):
            if len(next_digits) == 0:
                ans.append(combination)
            else:
                # 显式回溯：使用循环遍历数字对应的字母
                for letter in num_to_char[next_digits[0]]:
                    # 将当前字母加入组合
                    combination += letter
                    # 递归回溯，进入下一个数字
                    backtrack(combination, next_digits[1:])
                    # 显式回溯：移除上一个字母，恢复到原来的状态
                    combination = combination[:-1]

        if digits:
            backtrack("", digits)  # start with an empty string
        return ans

if __name__ == "__main__":
    digits = "23"
    print(Solution().letterCombinations(digits))

python

# 曾孜博 24工学院
class Solution:
    from collections import deque 
    def letterCombinations(self, digits: str) -> List[str]:
        k={'1':[],'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']}
        if not digits:
            return []
        r=deque([''])
        for x in digits:
            for _ in range(len(r)):
                pre=r.popleft()
                for y in k[x]:
                    cur=pre+y
                    r.append(cur)
        return list(r)

17.电话号码的字母组合 ​

17.电话号码的字母组合