如何仅通过递归实现电话号码字母映射的组合生成功能？

实现思路 #

递归采用回溯思路，逐层处理每一位数字：

• 每一层递归对应处理输入数字串的第index位，current_str存储前面index位已经拼接完成的前缀字符串
• 当index等于数字串总长度时，说明所有位处理完成，将当前拼接好的完整字符串加入结果集
• 否则遍历当前数字对应的所有可选字母，将字母拼接到前缀后，递归处理下一位数字

参考代码（Python） #

首先定义数字到字母的映射表，对应题目给出的规则：
digit_map = ["", "", "ABC", "DEF", "GHI", "JKL", "MNO", "PQRS", "TUV", "WXYZ"]

完整函数实现：

def letter_combinations(digits: str) -> list[str]:
    result = []
    if not digits:
        return result

    def backtrack(index: int, current_str: str) -> None:
        # 终止条件：所有位处理完成，保存结果
        if index == len(digits):
            result.append(current_str)
            return
        # 获取当前数字对应的字母列表
        current_digit = int(digits[index])
        available_letters = digit_map[current_digit]
        # 0和1无对应字母，直接返回无有效组合
        if not available_letters:
            return
        # 遍历所有可选字母，递归处理下一位
        for letter in available_letters:
            backtrack(index + 1, current_str + letter)
    
    backtrack(0, "")
    return result

常见问题说明 #

你之前得到短字符串的核心原因是递归中途就收集了未完成的拼接结果，本实现只有触发终止条件时才会保存最终结果，所有输出字符串的长度和输入数字串长度完全一致。测试输入"2629327"时，返回结果包含所有7位长度的字母组合，会覆盖你预期的COBWEBS、BOAWEBS等结果。

内容的提问来源于stack exchange，提问作者user11093215