leetcode BFS解题思路

时间:2021-03-29 09:30:10
  1. Word Ladder
    思路一:单向bfs, 使用visited数组记录哪些已经访问过了, 访问过的就不允许再次入队, 同时这里想到的是使用26个英文字母,枚举可能的取值, 类似brute force
    思路二:双向bfs,使用两个set,这里没有使用queue,是因为需要在queue里查询,不方便.
    另外,需要注意的一点是,每次遍历时,都是取size较小的来做搜索,初始时,各插入头和尾,之后每次取最小的set来拓展, 这样就实现了交替访问两个set,
    是两者的高度在 l/2, 这样可以缩短一般的时间