This is the 14th day of my participation in Gwen Challenge
Recently, I want to sort out my experience of brush algorithm. On the one hand, I want to review and consolidate. On the other hand, I also hope that my sharing can help more friends in learning algorithm.
The column is called “Algorithm Tips”, which will focus on the entirety of the algorithm, but will not cover all aspects. It is suitable for people with some algorithm experience to read.
This time we will focus on DFS and BFS. All the questions and source code of this part are uploaded to github. The solution is mainly implemented in Python.
An overview of the
The depth-first Search algorithm (DFS) is an algorithm used to traverse or Search a tree or graph. The process is simply as deep as possible into each branch path, and each node can only be accessed once.
Breadth First Search algorithm (embosses-first Search, abbreviated as BFS), also known as width First Search, is a graphic Search algorithm. Simply put, BFS starts at the root and traverses the tree’s width. If all nodes are accessed, the algorithm is aborted.
I put them together because a lot of problems can do both of these things, but they just go in different directions.
The ideas involved in this are already covered in the recursion section, but today we’ll focus on DFS and BFS in action.
The code template
Recursive writing of DFS
visited = set(a)def dfs(node, visited) :
if node in visited: # terminator
# already visited
return
visited.add(node)
# process current node here..for next_node in node.children():
if not next_node in visited:
dfs(next_node, visited)
Copy the codeNonrecursive writing of DFS
def DFS(self, tree) :
if tree.root is None:
return []
visited, stack = [], [tree.root]
while stack:
node = stack.pop()
visited.add(node)
process (node)
nodes = generate_related_nodes(node)
stack.push(nodes)
# other processing work.Copy the codeBFS spelled
def BFS(graph, start, end) :
queue = []
queue.append([start])
visited.add(start)
while queue:
node = queue.pop()
visited.add(node)
process(node)
nodes = generate_related_nodes(node)
queue.push(nodes)
# other processing work.Copy the code200. Number of islands
Let’s start with this classic DFS question, 200. Number of islands.
Here's a chance for you'1'Land) and'0'(water), please count the number of islands in the grid. Islands are always surrounded by water, and each island can only be formed by connecting adjacent lands horizontally and/or vertically. Furthermore, you can assume that all four sides of the grid are surrounded by water. The sample1Input: grid = [["1"."1"."1"."1"."0"],
["1"."1"."0"."1"."0"],
["1"."1"."0"."0"."0"],
["0"."0"."0"."0"."0"] output:1
Copy the codeWe can go through this matrix, and if we get a 1, we’re going to increase the number of islands by 1, and we’re going to change all of the islands, including this 1 and all of the neighboring ones, to 0.
So according to this idea quickly write DFS solution.
class Solution:
def numIslands(self, grid: List[List[str]]) - >int:
def _dfs(i, j) :
grid[i][j] = "0"
for dx, dy in directions:
n_i, n_j = i + dx, j + dy
if 0 <= n_i < row and 0 <= n_j < col and grid[n_i][n_j] == "1":
_dfs(n_i, n_j)
count = 0
row, col = len(grid), len(grid[0])
directions = [[-1.0], [1.0], [0.1], [0, -1]]
for i in range(row):
for j in range(col):
if grid[i][j] == "1":
count += 1
_dfs(i, j)
return count
Copy the codeAnother point to note is that the way I have written above changes the original array. If you don’t want to change the original array, you can use the Visited collection to store all the visited elements.
class Solution:
def numIslands(self, grid: List[List[str]]) - >int:
def _dfs(i, j) :
visited.add((i, j))
for m, n in direction:
if 0 <= i+m < row and 0 <= j+n < col and grid[i+m][j+n] == '1' and (i+m, j+n) not in visited:
_dfs(i+m, j+n)
if not grid or not grid[0] :return 0
direction = [(-1.0), (1.0), (0, -1), (0.1)]
row, col = len(grid), len(grid[0])
visited = set()
count = 0
for i in range(row):
for j in range(col):
if grid[i][j] == '1' and (i, j) not in visited:
count += 1
_dfs(i, j)
return count
Copy the codeThe DFS that we’re currently using when we’re flattening the island, and we can also use BFS here, with Queue, we’re using a kind of ripple spread to traverse the neighboring 1.
class Solution:
def numIslands(self, grid: List[List[str]]) - >int:
direction = [(1.0), (0.1), (-1.0), (0, -1)]
row = len(grid)
col = len(grid[0])
count = 0
for i in range(row):
for j in range(col):
if grid[i][j] == '1':
count += 1
# take the greedy principle, here can be set to 0 first 0
grid[i][j] = '0'
queue = [(i, j)]
while queue:
a, b = queue.pop(0)
for m, n in direction:
if 0 <= a+m < row and 0 <= b+n < col and grid[a+m][b+n] == '1':
queue.append((a+m, b+n))
grid[a+m][b+n] = '0'
return count
Copy the codeThis problem can also be used and look up the set of ideas to do, about and look up the set, there will be special topics behind.
class Solution:
def numIslands(self, grid: List[List[str]]) - >int:
if not grid or not grid[0] :return 0
uf = UnionFind(grid)
direction = [(-1.0), (1.0), (0, -1), (0.1)]
row, col = len(grid), len(grid[0])
for i in range(row):
for j in range(col):
if grid[i][j] == '0':
continue
for d in direction:
nr, nc = i+d[0], j+d[1]
if 0 <= nr < row and 0 <= nc < col and grid[nr][nc] == '1':
uf.union(i*col+j, nr*col+nc)
return uf.count
class UnionFind:
def __init__(self, grid) :
m, n = len(grid), len(grid[0])
self.count = 0
self.parent = [-1] * (m*n)
self.rank = [0] * (m*n)
for i in range(m):
for j in range(n):
if grid[i][j] == '1':
self.parent[i*n+j] = i*n+j
self.count += 1
def find(self, i) :
ifself.parent[i] ! = i: self.parent[i] = self.find(self.parent[i])return self.parent[i]
def union(self, x, y) :
rootx = self.find(x)
rooty = self.find(y)
ifrootx ! = rooty: self.parent[rootx] = rooty self.count -=1
Copy the code130. The surrounding area
To strike while the iron is hot, let’s look at the area around 130.
Given an m x n matrix board, consisting of characters' x 'and 'O', find all the regions surrounded by' x 'and fill all the 'O' in those regions with' x '. Example 1: input: board = [[" X ", "X", "X", "X"], [" X ", "O", "O", "X"], [" X ", "X", "O", "X"], [" X ", "O", "X", "X"]] output: [[" X ", "X", "X", "X"], [" X ", "X", "X", "X"], [" X ", "X", "X", "X"], [" X ", "O", "X", "X"]] : The bounded interval does not exist on the boundary, in other words, 'O' on any boundary will not be filled with 'X'. Any 'O' that is not on the boundary, or is not connected to the 'O' on the boundary, will eventually be filled with 'X'. Two elements are said to be "contiguous" if they are adjacent horizontally or vertically.Copy the codeThe number of islands in front of this problem have the same effect, the difference is that the problem is just “O” on the edge of the traversal, and the edge of the “O” and its adjacent position “O” marked as other letters such as “#”, when the rest of the “O” is at the center of all, to mark them as “X”, and then change the “#” to “O”.
DFS solution:
class Solution:
def solve(self, board: List[List[str]]) - >None:
""" Do not return anything, modify board in-place instead. """
def _dfs(i, j) :
if i < 0 or j < 0 or i >= len(board) or j >= len(board[0]) or board[i][j] in ['X'.The '#'] :return
board[i][j] = The '#'
_dfs(i-1, j)
_dfs(i+1, j)
_dfs(i, j-1)
_dfs(i, j+1)
if not board or not board[0] :return
m, n = len(board), len(board[0])
for i in range(0, m):
for j in range(0, n):
is_edge = i == 0 or j == 0 or i == m-1 or j == n-1
if is_edge and board[i][j] == 'O':
_dfs(i, j)
print(board)
for i in range(0, m):
for j in range(0, n):
if board[i][j] == 'O':
board[i][j] = 'X'
if board[i][j] == The '#':
board[i][j] = 'O'
Copy the codeBFS solution:
import collections
class Solution:
def solve(self, board: List[List[str]]) - >None:
if not board:
return
n, m = len(board), len(board[0])
que = collections.deque()
for i in range(n):
if board[i][0] = ="O":
que.append((i, 0))
if board[i][m - 1] = ="O":
que.append((i, m - 1))
for i in range(m - 1) :if board[0][i] == "O":
que.append((0, i))
if board[n - 1][i] == "O":
que.append((n - 1, i))
while que:
x, y = que.popleft()
board[x][y] = "A"
for mx, my in [(x - 1, y), (x + 1, y), (x, y - 1), (x, y + 1)]:
if 0 <= mx < n and 0 <= my < m and board[mx][my] == "O":
que.append((mx, my))
for i in range(n):
for j in range(m):
if board[i][j] == "A":
board[i][j] = "O"
elif board[i][j] == "O":
board[i][j] = "X"
Copy the code127. Solitaire
Next, let’s challenge a difficult question, 127
The conversion sequence from beginWord to endWord in the dictionary wordList is a sequence formed according to the following specification: the first word in the sequence is beginWord. The last word in the sequence is endWord. Only one letter can be changed per conversion. The intermediate word in the conversion process must be a word in the dictionary wordList. Given two words beginWord and endWord and a dictionary wordList, find the number of words in the shortest conversion sequence from beginWord to endWord. If no such conversion sequence exists, return 0. Example 1: Input: beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"] output: 5 A minimum conversion sequence is "hit" - > "hot" - > "dot" - > "dog" - > "cog", return it the length of 5.Copy the codeSince it requires the shortest transformation sequence, it is not suitable to use DFS (DFS can calculate the result, but the first result is not necessarily the optimal solution, it must be all recursed), we use BFS to do it.
class Solution:
def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) - >int:
wordList = set(wordList)
queue = [(beginWord, 1)]
while queue:
word, length = queue.pop(0)
if word == endWord:
return length
for i in range(len(word)):
for c in "abcdefghijklmnopqrstuvwxyz":
next_word = word[:i] + c + word[i+1:]
if next_word in wordList:
queue.append((next_word, length+1))
wordList.remove(next_word)
return 0
Copy the codeChange it one character at a time, and if it’s in a single set, put it in the queue and add the sequence length +1 until we find our answer first.
We can optimize this problem, we can see that the end and the beginning are symmetric, if we can BFS from the beginning, why can’t we BFS from the end.
So we can do BFS from the beginning and the end until they meet, which is also called bidirectional BFS.
class Solution:
def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) - >int:
if endWord not in wordList: return 0
front = {beginWord}
back = {endWord}
dist = 1
wordList = set(wordList)
word_len = len(beginWord)
while front:
dist += 1
next_front = set(a)for word in front:
for i in range(word_len):
for c in string.ascii_lowercase:
ifc ! = word[i]: new_word = word[:i] + c + word[i+1:]
if new_word in back:
return dist
if new_word in wordList:
next_front.add(new_word)
wordList.remove(new_word)
front = next_front
if len(back) < len(front):
front, back = back, front
return 0
Copy the codeNotice that in the algorithm, we compare the queue lengths of the start and end to determine whether to use the start or end queue next time.
433. Minimal genetic changes
Finally, we use this problem to consolidate DFS and BFS. 433. Minimal genetic changes.
A gene sequence is represented by A string of eight characters, each of which belongs to one of "A", "C", "G" or "T". Suppose we want to investigate changes in a gene sequence. A genetic change means that a character in that gene sequence has changed. For example, a genetic change occurs when a gene sequence changes from "AACCGGTT" to "AACCGGTA". At the same time, the result of each genetic change needs to be a legitimate gene string, meaning that the result belongs to a gene pool. Given three parameters -- start, end and Bank, which respectively represent the initial gene sequence, the target gene sequence and the gene pool, please find the minimum number of changes required to make the initial gene sequence change into the target gene sequence. If the target change cannot be achieved, return -1. Note: The initial gene sequence is legal by default, but it does not necessarily appear in the gene bank. If a starting gene sequence requires multiple changes, the sequence that follows each change must be legitimate. The initial gene sequence is assumed to be different from the target gene sequence. Example 1: start: "AACCGGTT" End: "AACCGGTA" Bank: ["AACCGGTA"] Returned value: 1Copy the codeLet’s start with DFS.
class Solution:
def minMutation(self, start: str, end: str, bank: List[str]) - >int:
bank = set(bank)
if end not in bank:
return -1
change_map = {
"A": "CGT"."C": "AGT"."G": "CAT"."T": "CGA",
}
min_count = len(bank) + 1
def dfs(current, count, current_bank) :
nonlocal min_count
# terminator
if count > min_count:
return
if current == end:
if count < min_count:
min_count = count
return
if not current_bank:
return
# process
for i, s in enumerate(current):
for char in change_map[s]:
new = current[:i] + char + current[i + 1:]
if new not in current_bank:
continue
current_bank.remove(new)
# drill down
dfs(new, count + 1, current_bank)
# reverse state
current_bank.add(new)
dfs(start, 0, bank)
return min_count if min_count <= len(bank) else -1
Copy the codeAnd then the BFS
class Solution:
def minMutation(self, start, end, bank) :
queue = [(start, 0)]
bank = set(bank)
while queue:
cur, count = queue.pop(0)
if cur == end: return count
for i in range(0.len(start)):
for ch in ['A'.'C'.'G'.'T']:
new = cur[0:i] + ch + cur[i+1:]
if new in bank:
queue.append((new, count+1))
bank.remove(new)
return -1
Copy the codeAnd, of course, you could use bidirectional BFS
class Solution:
def minMutation(self, start: str, end: str, bank: List[str]) - >int:
if end not in bank:
return -1
start_set = {start}
end_set = {end}
bank = set(bank)
length = 0
change_map = {'A': 'TCG'.'T': 'ACG'.'C': 'ATG'.'G': 'ATC'}
while start_set:
length += 1
new_set = set(a)for node in start_set:
for i, s in enumerate(node):
for c in change_map[s]:
new = node[:i] + c + node[i + 1:]
if new in end_set:
return length
if new in bank:
new_set.add(new)
bank.remove(new)
start_set = new_set
if len(end_set) < len(start_set):
start_set, end_set = end_set, start_set
return -1
Copy the code