LeetCode 126: Word Ladder II Python代码超时优化求助

• 预构建通配符映射：别每次对单词逐个替换字符生成变异词再查字典，提前给所有单词生成通配形式（如把"hot"转为"ot"、"ht"、"ho*"），建立通配符 -> 对应单词列表的映射。找邻居时直接查该单词所有通配符对应的单词，比逐个字符替换+集合查询快数倍，能大幅减少字符操作和查询耗时。

• 层级批量去重：BFS时不要处理一个单词就立刻从候选集合中移除，而是把当前层级所有单词收集到一个临时集合，处理完整个层级后再一次性从候选集合中删除。这样避免同一层级内的单词互相屏蔽，同时减少集合操作的次数，提升效率。

• 双向BFS+路径回溯：改用双向BFS，同时从起点和终点向中间搜索，当两边的搜索集合相交时停止，能大幅减少搜索的总节点数。另外，不要在BFS队列中存储完整路径，而是记录每个单词的前驱（或后继）节点映射，最后从终点回溯到起点生成所有路径，避免大量路径复制的开销。

• 优化数据结构与操作：

  • 用deque代替列表做BFS队列，popleft()操作是O(1)，远快于列表pop(0)的O(n)。
  • 单词字典用集合存储，保证O(1)的查询速度。
  • 预先计算单词长度，避免在循环中重复调用len(word)。
  • 尽量用生成器或列表推导式代替循环拼接字符串，减少内存占用和操作时间。

• 提前终止搜索：当BFS搜索到包含终点的层级后，直接停止后续层级的搜索，不用再继续遍历更深的节点，避免无效计算。

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