2.BFS

模板

# 广度优先搜索分需要记忆层数的和不需要记忆层数的两种
#1.不需要记忆层数
while queue 不空：
    cur = queue.pop()
    if cur 有效且未被访问过：
        进行处理
    for 节点 in cur 的所有相邻节点：
        if 该节点有效：
            queue.push(该节点)

#2.需要记忆层数，引入level表示层数，size表示该层元素个数，遍历完一层level+1
level = 0
while queue 不空：
    size = queue.size()
    while(size --)：
        cur = queue.pop()
        if cur 有效且未被访问过：
            进行处理
        for 节点 in cur的所有相邻节点：
            if 该节点有效：
                queue.push(该节点)
    level+=1

例题1

力扣433

# 由于本题需要知道变换了多少次，因此需要确定当前遍历到哪一层，故本题中直接套用模板二。
'''
代码总体思路：
    利用队列保存有效的字符串
    只要队列不空，就持续循环：
        记录当前队列的长度，对队列中该长度的字符串逐一遍历：
            如果搜索到 end，直接返回当前的步数 step
            否则，对当前字符串中的每个字符，都转变成 ACGT四个字符，看新形成的字符串是否遇到过
            如果没遇到过，就放入队列之中。
        步数 + 1
其中判断字符串是否遇到过：直接从 bank 中删除已经遇到过的字符串。
'''
class Solution(object):
    def minMutation(self, start, end, bank):
        """
        :type start: str
        :type end: str
        :type bank: List[str]
        :rtype: int
        """
        bfs = collections.deque()
        bfs.append((start, 0))
        bankset = set(bank)
        while bfs:
            gene, step = bfs.popleft()
            if gene == end:
                return step
            for i in range(len(gene)):
                for x in "ACGT":
                    newGene = gene[:i] + x + gene[i+1:]
                    if newGene in bank and newGene != gene:
                        bfs.append((newGene, step + 1))
                        bank.remove(newGene)
        return -1

例题2

力扣127

# 和上面的一摸一样
class Solution:
    def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:
        bfs=collections.deque()
        bfs.append((beginWord,0))
        wordList=set(wordList)
        while bfs:
            word,step=bfs.popleft()
            if word==endWord:
                return step+1
            for i in range(len(word)):
                for x in 'abcdefghijklmnopqrstuvwxyz':
                    newWord=word[:i]+x+word[i+1:]
                    if newWord in wordList and newWord!=word:
                        bfs.append((newWord,step+1))
                        wordList.remove(newWord)
        return 0