【力扣100】17.电话号码的字母组合

添加链接描述

class Solution:def letterCombinations(self, digits: str) -> List[str]:# 思路是使用回溯算法if not digits:return []phone = {'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']}def backtrack(con,dig):# 收获if len(dig)==0:res.append(con)else:for letter in phone[dig[0]]:backtrack(con+letter,dig[1:])res=[]backtrack('',digits)return res

思路：

1. 定义一个回溯函数，其中con参数是用来储存每一个路径值，最后就是叶子节点指向的值，dig是题目给的数组，这个数组会越来越小
2. dig数组越来越小，知道变成0，然后进行收获叶子节点

使用队列的解法

class Solution:def letterCombinations(self, digits: str) -> List[str]:if not digits: return []phone = ['abc','def','ghi','jkl','mno','pqrs','tuv','wxyz']queue = ['']  # 初始化队列for digit in digits:for _ in range(len(queue)):tmp = queue.pop(0)for letter in phone[ord(digit)-50]:# 这里我们不使用 int() 转换字符串，使用ASCII码queue.append(tmp + letter)return queue

解决的一个疑惑

queue=[0,1,2,3]
for i in range(len(queue)):print(i)queue.append(4)print(queue)

Q：这里因为queue的长度在不断改变，难么i的值也会无限增大下去吗？
A：不会，在这段代码中，虽然 queue 的长度在循环中不断增加，但 range(len(queue)) 在循环开始时就已经确定了。它是根据循环开始前 queue 的长度计算出来的，因此即使在循环过程中 queue 的长度增加了，range(len(queue)) 的值并不会随之改变。

当循环开始时，range(len(queue)) 会生成一个范围，它是根据 queue 的初始长度计算的，并且这个范围不会在循环执行过程中动态地更新。因此，即使在循环内部你不断地向 queue 中添加元素，for i in range(len(queue)) 仍然只会循环 queue 初始时的长度次数。

换句话说，range(len(queue)) 是在循环开始前计算的，所以循环次数在进入循环时就已经确定了，而不会受到循环内 queue 长度变化的影响。

0
[0, 1, 2, 3, 4]
1
[0, 1, 2, 3, 4, 4]
2
[0, 1, 2, 3, 4, 4, 4]
3
[0, 1, 2, 3, 4, 4, 4, 4]