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

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

一般涉及到最小层数问题,要想到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

单词接龙2

单向遍历
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
目录
打赏
0
0
0
0
115
分享
相关文章
|
4月前
|
Leetcode 初级算法 --- 数组篇
Leetcode 初级算法 --- 数组篇
59 0
LeetCode第75题颜色分类
文章介绍了LeetCode第75题"颜色分类"的解法,通过双指针技术对数组中的0、1和2进行排序,避免了传统的排序算法,提供了一种时间复杂度为O(n)的高效解决方案。
LeetCode第75题颜色分类
LeetCode第73题矩阵置零
文章介绍了LeetCode第73题"矩阵置零"的解法,通过使用矩阵的第一行和第一列作为标记来记录哪些行或列需要置零,从而在不增加额外空间的情况下解决问题。
LeetCode第73题矩阵置零
leetcode算法题-有效的括号(简单)
【11月更文挑战第5天】本文介绍了 LeetCode 上“有效的括号”这道题的解法。题目要求判断一个只包含括号字符的字符串是否有效。有效字符串需满足左括号必须用相同类型的右括号闭合,并且左括号必须以正确的顺序闭合。解题思路是使用栈数据结构,遍历字符串时将左括号压入栈中,遇到右括号时检查栈顶元素是否匹配。最后根据栈是否为空来判断字符串中的括号是否有效。示例代码包括 Python 和 Java 版本。
作业调度算法_先来先服务算法_短作业优先算法_高响应比优先算法
本文介绍了作业调度算法,包括先来先服务(FCFS)、短进程优先(SJF)和高响应比优先(HRRN)算法。通过分析进程的到达时间和所需CPU服务时间,计算进程的开始时间、完成时间、平均周转时间和平均带权周转时间,以评估不同算法的性能。FCFS适合长作业,SJF适合短作业,而HRRN则综合了两者的优点。
217 12
|
6月前
|
测试工程师的技能升级:LeetCode算法挑战与职业成长
这篇文章通过作者亲身体验LeetCode算法题的过程,探讨了测试工程师学习算法的重要性,并强调了算法技能对于测试职业成长的必要性。
105 1
测试工程师的技能升级:LeetCode算法挑战与职业成长
|
4月前
|
Leetcode第59题(螺旋矩阵2)
这篇文章介绍了解决LeetCode第59题“螺旋矩阵II”的算法,通过C++编程实现按顺时针顺序填充一个n x n的正方形矩阵。
26 0
|
6月前
|
LeetCode经典算法题:矩阵中省份数量经典题目+三角形最大周长java多种解法详解
LeetCode经典算法题:矩阵中省份数量经典题目+三角形最大周长java多种解法详解
81 6
LeetCode经典算法题:打家劫舍java详解
LeetCode经典算法题:打家劫舍java详解
93 2
LeetCode经典算法题:井字游戏+优势洗牌+Dota2参议院java解法
LeetCode经典算法题:井字游戏+优势洗牌+Dota2参议院java解法
71 1

热门文章

最新文章

AI助理

你好,我是AI助理

可以解答问题、推荐解决方案等