拆解LeetCode电话号码的字母组合题中列表推导式嵌套for循环

初始思路代码 #

我最初的实现思路代码如下：

def letterCombinations(self, digits: str) -> List[str]:
    if not digits: return []
    digit_map = {'2': 'abc', '3': 'def', '4': 'ghi', '5': 'jkl', '6': 'mno', 
                 '7': 'pqrs', '8': 'tuv', '9': 'wxyz'}
    result = [""]
    arr = []
    for i in digits:
        for j in digit_map:
            if i==j:
                s = map(str,digit_map[i])
                for x in s:
                    arr.append(x)

该思路存在缺陷，后续我参考了公开题解的实现，题解代码如下：

def letterCombinations(self, digits: str) -> List[str]:
    if not digits: return []
    dt = {'2': 'abc', '3': 'def', '4': 'ghi', '5': 'jkl', '6': 'mno', '7': 'pqrs', '8': 'tuv', '9': 'wxyz'}
    rst = ['']
    for i in digits: rst = [j+k for j in rst for k in dt[i]]
    return rst

疑问与解答 #

我无法理解上述代码第5行的列表推导式逻辑，尝试改写为多行普通for循环后结果错误，我的错误改写如下：

for i in digits:
    tmp = []
    for j in rst:
        for k in dt[i]:
            temp = [j+k] 
    rst += temp

错误原因 #

你的改写存在两个核心问题：

• 没有将每次拼接得到的j+k存入临时数组，只存了最后一次循环的结果到temp变量
• 最终是将新生成的组合替换原来的rst，而不是追加到rst末尾

正确的多行改写版本 #

for i in digits:
    tmp = []
    # 遍历上一轮生成的所有字母组合
    for j in rst:
        # 遍历当前数字对应的每一个字母
        for k in dt[i]:
            # 拼接得到新组合，存入临时数组
            tmp.append(j + k)
    # 用新的组合列表替换旧的rst
    rst = tmp

逻辑示例（以输入digits = "23"为例） #

1. 初始状态rst = [""]
2. 遍历第一个数字2，对应字母abc：
   遍历rst里的空字符串，分别拼接a/b/c，得到新的rst = ["a", "b", "c"]
3. 遍历第二个数字3，对应字母def：
   遍历rst里的每个字符串，分别拼接d/e/f，最终得到rst = ["ad","ae","af","bd","be","bf","cd","ce","cf"]
   和原列表推导式的运行结果完全一致。

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