leetcode中DFS与BFS算法在数组和字符串中的应用

Zahirah ·

更新时间:2024-11-13

· 585 次阅读

DFS（深度优先遍历）与BFS（广度优先遍历）算法是基于树和图结构进行遍历的两种算法。
一般来说DFS在前中后遍历中运用比较明显，DFS的运用基本是要利用递归进行嵌套使用。回溯算法其实也是一种比较经典的DFS算法升级运用
而BFS比较经典的运用就是层次遍历，一般会运用数组和while循环不断进行pop和insert操作。

涉及到回溯算法和递归的二叉树结构题，之前已经进行过总结：
leetcode回溯算法
leetcode二叉树遍历与递归题目汇总

然而，对于字符串和数组类的结构，我自己在开始的时候很难将其与DFS和BFS算法结合起来。所以为了更深入的理解DFS和BFS算法的精髓，这里针对这些数据结构进一步汇总

BFS

BFS在计算最短或者最小等问题上相比DFS要简单很多，因为找到某层符合条件的一个即可停止。

1.字符串匹配问题

301. 删除无效的括号
找到删除最小括号可以满足的字符串，显然是横向对比只要较高层存在一个即可，故肯定是BFS的问题。
思路：1.理解何种字符串是符合要求的，并写出isValid函数判断
2.利用filter函数对字符串进行映射判断
3.利用while循环分别判断初始字符串减去一个字符的level，二个字符的level等情况的结果情况。不停地更新每一次的level情况

class Solution:
    def removeInvalidParentheses(self, s: str) -> List[str]:
        def isValid(s):
            cnt = 0
            for i in s:
                if i == '(':
                    cnt += 1
                elif i == ')':
                    cnt -= 1
                if cnt < 0:return False
            return cnt == 0
        level = {s}
        while level:
            valid = list(filter(isValid,level))
            if valid:return valid
            next_level = set()
            for item in level:
                for i in range(len(item)):
                	#只判定为括号的情况，其他情况不需要判定
                    if item[i] in '()':
                        next_level.add(item[:i] + item[i+1:])
            level = next_level

DFS 1.数组问题

6.岛屿的最大面积
典型的数组中的最大值问题，需要遍历每个单元找到最大值，故是DFS问题。

class Solution:
    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:
    	#用res[0]代表全局最大值，res[1]代表局部最大值
    	#确定初始参数
        res,r,c = [0,0],len(grid),len(grid[0])
        #定义dfs函数
        def f(i,j):
            res[1] += 1
            grid[i][j] = 0
            for x,y in [(i+1,j),(i-1,j),(i,j+1),(i,j-1)]:
                if 0<= x < r and 0<= y < c and grid[x][y]:
                    f(x,y)
        #循环遍历计算最大值
        for i,j in itertools.product(range(r),range(c)):
            if grid[i][j]:
                res[1] = 0
                f(i,j)
                res[0] = max(res)
        return res[0]

329. 矩阵中的最长递增路径
寻找最长路径其实思路和上题基本一致。设置初始化参数，并定义dfs函数后，循环调用dfs函数即可

def longestIncreasingPath(matrix):
	#单元测试
	if not matrix:
		return 0
	#初始化参数
	longest_path = 0
	rows = len(matrix)
	cols = len(matrix[0])
	cache = [[None] * cols for _ in range(rows)]
	#定义dfs函数
	def dfs(i: int, j: int):
		if cache[i][j]:
			return cache[i][j]
		Max = 0
		for x, y in [(i + 1, j), (i - 1, j), (i, j + 1), (i, j - 1)]:
			if 0 <= x < rows and 0 <= y  matrix[i][j]:
				Max = max(Max, 1 + dfs(x, y))
		cache[x][y] = Max
		return cache[x][y]
	#循环遍历计算最大值
	for x in range(rows):
		for y in range(cols):
			longest_path = max(longest_path, dfs(x, y))
	return longest_path

488. 祖玛游戏
这道题算是一道比较难的题，而且部分通过的代码其实没考虑"RRWWRRBBRR"
，"WB"这种情况。
先贴一个ac的效率较高的代码

from collections import Counter
from itertools import groupby
from heapq import heappush, heappop
def chunks(board):
    return [''.join(g) for _, g in groupby(board)]
class Solution:
    def findMinStep(self, board, hand):
        counts = Counter(hand)
        queue = []
        heappush(queue, (0, board, counts))
        while len(queue) > 0:
            (count, current_board, hand_counts) = heappop(queue)
            board_chunks = chunks(current_board)
            if len(board_chunks) == 0:
                return count
            for i in range(len(board_chunks)):
                chunk_char = board_chunks[i][0]
                chunk_len = len(board_chunks[i])
                hand_count = hand_counts.get(chunk_char, 0)
                need_count = max(0, 3 - chunk_len)
                assert(hand_count >= 0)
                if need_count <= hand_count:
                    next_hand_counts = hand_counts.copy()
                    next_hand_counts[chunk_char] = hand_count - need_count
                    next_board = ''.join(board_chunks[0:i] + board_chunks[i + 1:])
                    heappush(queue, (count + need_count, next_board, next_hand_counts))
        return -1

2.序列问题

491. 递增子序列
很典型的DFS回溯算法应用。需要写清楚终止条件和递归条件

class Solution:
    def findSubsequences(self, nums: List[int]) -> List[List[int]]:
        result = []
        def dfs(nums,List,idx):
            if idx >= len(nums):
                if len(List) >= 2:
                    #注意这里使用深拷贝
                    result.append(List[:])
                return
            if len(List) == 0 or nums[idx] >= List[-1]:
                #回溯算法进行判断
                List.append(nums[idx])
                dfs(nums,List,idx + 1)
                List.pop()
            #这里的逻辑主要是避免上面添加过的数字再添加一次
            if idx > 0 and len(List) != 0 and nums[idx] == List[-1]:
                return
            dfs(nums,List,idx + 1)
        dfs(nums,[],0)
        return result