【经典LeetCode算法题目专栏分类】【第4期】BFS广度优先算法：单词接龙、最小基因变化、二进制矩阵中的最短路径

#?单向BFS

class?Solution:

????def?ladderLength(self,?beginWord:?str,?endWord:?str,?wordList:?List[str])?->?int:

????????queue =?[(beginWord,?1)]

????????word_list =?[?chr(ord('a')?+?i)?for?i in?range(27)]

????????wordList =?set(wordList)

????????n =?len(beginWord)

????????while?queue:

????????????word,?step =?queue.pop(0)

????????????if?word ==?endWord:

????????????????return?step

????????????for?i in?range(n):

????????????????for?c in?word_list:

????????????????????tmp =?word[:i]?+?c +?word[i+1:]

????????????????????if?tmp in?wordList:

????????????????????????wordList.remove(tmp)

????????????????????????queue.append((tmp,?step +?1))

????????return?0

# 双向BFS

class?Solution:

????def?ladderLength(self,?beginWord:?str,?endWord:?str,?wordList:?List[str])?->?int:

????????#?双向BFS

????????word_set?=?set(wordList)

????????if?len(word_set)?==?0?or?endWord?not?in?word_set:

????????????return?0

????????if?beginWord?in?word_set:

????????????word_set.remove(beginWord)

????????visited?=?set()

????????visited.add(beginWord)

????????visited.add(endWord)

????????begin_visited?=?set()

????????begin_visited.add(beginWord)

????????end_visited?=?set()

????????end_visited.add(endWord)

????????word_len?=?len(beginWord)

????????step?=?1

????????#?简化成?while?begin_visited?亦可

????????while?begin_visited?and?end_visited:

????????????if?len(begin_visited)?>?len(end_visited):

????????????????begin_visited,?end_visited?=?end_visited,?begin_visited

????????????next_level_visited?=?set()

????????????for?word?in?begin_visited:

????????????????word_list?=?list(word)

????????????????for?j?in?range(word_len):

????????????????????origin_char?=?word_list[j]

????????????????????for?k?in?range(26):

????????????????????????word_list[j]?=?chr(ord('a')?+?k)

????????????????????????next_word?=?''.join(word_list)

????????????????????????if?next_word?in?word_set:

????????????????????????????if?next_word?in?end_visited:

????????????????????????????????return?step?+?1

????????????????????????????if?next_word?not?in?visited:

????????????????????????????????next_level_visited.add(next_word)

????????????????????????????????visited.add(next_word)

????????????????????word_list[j]?=?origin_char

????????????begin_visited?=?next_level_visited

????????????step?+=?1

????????return?0

单向遍历

class?Solution:

????def?findLadders(self,?beginWord:?str,?endWord:?str,?wordList:?List[str])?->?List[List[str]]:

????????tree,?words,?n =?collections.defaultdict(set),?set(wordList),?len(beginWord)?

????????if?endWord not?in?wordList:?return?[]

????????# found为是否找到最短路径的标识默认False

????????# q存储当前层的单词， nq存储下一层的单词

????????# tree[x]会记录单词x所有相邻节点的单词，即可能到达最终结果的路径

????????found,?q,?nq =?False,?{beginWord},?set()

????????while?q and?not?found:?# 当找到路径或者队列中没有元素时结束

????????????words -=?set(q)?# 从words列表中去除当前层的单词，避免重复使用

????????????for?x in?q:?# 遍历当前层的所有单词

????????????????for?y in?[x[:i]+c+x[i+1:]?for?i in?range(n)?for?c in?'qwertyuiopasdfghjklzxcvbnm']:?# 改变当前单词的每一个字符

????????????????????if?y in?words:?# 只关心在words集合中的单词

????????????????????????if?y ==?endWord:?# 如果找到了，将found置为True，不会再继续寻找下一层.

????????????????????????????found =?True

????????????????????????else:?

????????????????????????????nq.add(y)?# 准备下一层的单词集合

????????????????????????tree[x].add(y)?# 记录x单词满足条件的下一个路径

????????????q,?nq =?nq,?set()?# 重新复制q与nq, q为下一次循环需遍历的单词集合,nq置为空

????????def?bt(x):?

????????????# 递归，在tree中寻找满足条件的路径

????????????# for y in tree[x] 遍历当前单词的相邻节点

????????????return?[[x]]?if?x ==?endWord else?[[x]?+?rest for?y in?tree[x]?for?rest in?bt(y)]

????????if?found ==?False:

????????????return?[]

????????return?bt(beginWord)

#?双向遍历

class?Solution:

????def?findLadders(self,?beginWord:?str,?endWord:?str,?wordList:?List[str])?->?List[List[str]]:

????????# 双向BFS

????????tree,?words,?n =?collections.defaultdict(set),?set(wordList),?len(beginWord)

????????if?endWord not?in?wordList:?return?[]

????????found,?bq,?eq,?nq,?rev =?False,?{beginWord},?{endWord},?set(),?False

????????while?bq and?not?found:

????????????words -=?set(bq)

????????????for?x in?bq:

????????????????for?y in?[x[:i]+c+x[i+1:]?for?i in?range(n)?for?c in?'qwertyuiopasdfghjklzxcvbnm']:

????????????????????if?y in?words:

????????????????????????if?y in?eq:?

????????????????????????????found =?True

????????????????????????else:?

????????????????????????????nq.add(y)

????????????????????????tree[y].add(x)?if?rev else?tree[x].add(y)

????????????bq,?nq =?nq,?set()

????????????if?len(bq)?>?len(eq):?

????????????????bq,?eq,?rev =?eq,?bq,?not?rev

????????def?bt(x):?

????????????return?[[x]]?if?x ==?endWord else?[[x]?+?rest for?y in?tree[x]?for?rest in?bt(y)]

????????return?bt(beginWord)

class?Solution:

????def?minMutation(self,?start:?str,?end:?str,?bank:?List[str])?->?int:

????????#BFS

????????possible_dict =?{

????????????????????????"A":?"CGT",

????????????????????????"C":?"AGT",

????????????????????????"G":?"ACT",

????????????????????????"T":?"ACG"

????????????????????}

????????queue=[(start,0)]

????????while?queue:

????????????# 广度优先遍历模板

????????????(word,?step)=queue.pop(0)

????????????if?word ==end:

????????????????return?step

????????????

????????????for?i,?c ?in?enumerate(word):

????????????????for?p in?possible_dict[c]:

????????????????????# 从第0个位置开始匹配新的字符串

????????????????????temp=word[:i]+p+word[i+1:]

????????????????????# 在bank里面就处理(set中in操作复杂度是0(1))

????????????????????if?temp in?bank:?

????????????????????????# 从bank里移除，避免重复计数

????????????????????????bank.remove(temp)??

????????????????????????# 加入队列，步数加1

????????????????????????queue.append((temp,step+1))?

????????return?-1

class?Solution:

????def?shortestPathBinaryMatrix(self,?grid:?List[List[int]])?->?int:

????????# BFS

????????n =?len(grid)

????????if?grid[n-1][n-1]?==?1?or?grid[0][0]?==?1:

????????????return?-1

????????queue =?[(0,0)]

????????length =?1

????????visited =?set()

????????visited.add((0,0))

????????while?queue:

????????????cur_nums =?len(queue)

????????????for?i in?range(cur_nums):

????????????????i,j =?queue.pop(0)

????????????????if?i ==?n-1?and?j ==?n-1:

????????????????????return?length

????????????????for?ni,nj in?[(i-1,j-1),(i-1,j),(i-1,j+1),(i,j-1),(i,j+1),(i+1,j-1),(i+1,j),(i+1,j+1)]:

????????????????????if?0<=?ni <?n and?0<=?nj <?n and?(ni,nj)?not?in?visited and?grid[ni][nj]?==?0:

????????????????????????visited.add((ni,nj))

????????????????????????queue.append((ni,nj))

????????????length +=?1

????????return?-1