17. 电话号码的字母组合(Medium)

题目描述

给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。注意 1 不对应任何字母。

样例

Input："23"
Output：["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].

题目解析

本题可以使用多重循环来写，以 "232" 为例

for s1 in "abc":
   for s2 in "def"
     for s3 in "abc":
        ans.append(s1 + s2 + s3)

但是这样的多重循环编写代码很困难，就需要使用 递归 + 迭代 实现。

本题和其他组合题目的区别

「因为本题每一个数字代表的是不同集合，也就是求不同集合之间的组合，而77. 组合和216.组合总和III都是是求同一个集合中的组合！」

Python 代码示例

def backtracking(digits, letterMap, ans, level, tmp):
    if level >= len(digits): # 遍历结束
        ans.append(tmp)
        return 
    
    number = int(digits[level])
    for i in range(len(letterMap[number])):
        tmp += letterMap[number][i]
        backtracking(digits, letterMap, ans, level + 1, tmp)
        tmp = tmp[:-1]
    
class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
        if not digits: return [] # 空
        letterMap = [
            "",
            "",
            "abc",
            "def",
            "ghi",
            "jkl",
            "mno",
            "pqrs",
            "tuv",
            "wxyz"
        ]
        ans = []
        backtracking(digits, letterMap,  ans, 0, "")
        return ans 

参考资料

1. 回溯算法：电话号码的字母组合