【leetcode刷题之路】面试经典150题（6）——图+图的广度优先搜索+字典树+回溯

文章目录

• • • 12 图
    • • 12.1 【DFS】岛屿数量
      • 12.2 【DFS】被围绕的区域
      • 12.3 【DFS】克隆图
      • 12.4 【DFS】除法求值
      • 12.5 【DFS】【拓扑排序】课程表
      • 12.6 【DFS】【拓扑排序】课程表 II
    • 13 图的广度优先搜索
    • • 13.1 【BFS】蛇梯棋
      • 13.2 【BFS】最小基因变化
      • 13.3 【双向BFS】单词接龙
    • 14 字典树
    • • 14.1 【Trie】实现 Trie (前缀树)
      • 14.2 【DFS】【Trie】添加与搜索单词 - 数据结构设计
      • 14.3 【Trie】【DFS】单词搜索 II
    • 15 回溯
    • • 15.1 【DFS】电话号码的字母组合
      • 15.2 【DFS】组合
      • 15.3 【DFS】全排列
      • 15.4 【DFS】【剪枝】组合总和
      • 15.5 【DFS】【剪枝】N 皇后 II
      • 15.6 【DFS】【剪枝】括号生成
      • 15.7 【DFS】单词搜索

12 图

12.1 【DFS】岛屿数量

题目地址：https://leetcode.cn/problems/number-of-islands/description/?envType=study-plan-v2&envId=top-interview-150

  遍历图中所有的位置，如果该位置为$1$，则向外扩展将与之相连的$1$全部变为$0$，记录需要进行扩展的$1$的个数。

class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        row = len(grid)
        col = len(grid[0])
        ans = 0

        def DFS(i,j):
            grid[i][j] = "0"
            for x,y in [[0,1],[1,0],[0,-1],[-1,0]]:
                tmp_i = i + x
                tmp_j = j + y
                if 0 <= tmp_i < row and 0 <= tmp_j < col and grid[tmp_i][tmp_j] == "1":
                    DFS(tmp_i,tmp_j)
        
        for i in range(row):
            for j in range(col):
                if grid[i][j] == "1":
                    DFS(i,j)
                    ans += 1
        return ans

12.2 【DFS】被围绕的区域

题目地址：https://leetcode.cn/problems/surrounded-regions/description/?envType=study-plan-v2&envId=top-interview-150

  反向思考，与边界的$O$相连的位置如果也是$O$，则这些位置一定不会被覆盖，所以从区域边界向内$DFS$，找出所有不会被覆盖的位置，再将区域内剩下的$O$覆盖为$X$即可。

class Solution:
    def solve(self, board: List[List[str]]) -> None:
        row = len(board)
        col = len(board[0])

        def DFS(i,j):
            if 0 <= i < row and 0 <= j < col and board[i][j] == "O":
                board[i][j] = "#"
                for x,y in [[0,1],[0,-1],[-1,0],[1,0]]:
                    tmp_i = i + x
                    tmp_j = j + y
                    DFS(tmp_i,tmp_j)
        
        for i in range(row):
            DFS(i,0)
            DFS(i,col-1)
        for j in range(col):
            DFS(0,j)
            DFS(row-1,j)
        
        for i in range(row):
            for j in range(col):
                if board[i][j] == "O":
                    board[i][j] = "X"
                elif board[i][j] == "#":
                    board[i][j] = "O"

12.3 【DFS】克隆图

题目地址：https://leetcode.cn/problems/clone-graph/description/?envType=study-plan-v2&envId=top-interview-150

  该题与克隆链表比较像，重点在于如何把每个结点的$neighbors$全部克隆下来，这里需要额外引入一个字典来防止图中结点被重复访问，然后按照图中结点进行深度优先遍历即可。

"""
# Definition for a Node.
class Node:
    def __init__(self, val = 0, neighbors = None):
        self.val = val
        self.neighbors = neighbors if neighbors is not None else []
"""

from typing import Optional
class Solution:
    def cloneGraph(self, node: Optional['Node']) -> Optional['Node']:
        self.node_list = {}

        def DFS(node):
            if not node:
                return
            if node in self.node_list:
                return self.node_list[node]
            new_node = Node(node.val, [])
            self.node_list[node] = new_node
            for n in node.neighbors:
                new_node.neighbors.append(DFS(n))
            return new_node

        return DFS(node)

12.4 【DFS】除法求值

题目地址：https://leetcode.cn/problems/evaluate-division/description/?envType=study-plan-v2&envId=top-interview-150

  这道题的核心是根据$equations$和$values$构造一个有向图，然后查找$queries$中的每对字母之间是否存在一条路径，如果存在就返回这条路径上的所有权重的乘积，否则就返回$-1$。

class Solution:
    def calcEquation(self, equations: List[List[str]], values: List[float], queries: List[List[str]]) -> List[float]:
        graph = {}

        # graph_construction
        for (x,y),v in zip(equations,values):
            if x in graph:
                graph[x][y] = v
            else:
                graph[x] = {y:v}
            if y in graph:
                graph[y][x] = 1/v
            else:
                graph[y] = {x:1/v}

        # DFS
        def DFS(start,end):
            if start not in graph:
                return -1
            if start == end:
                return 1
            for node in graph[start].keys():
                if node == end:
                    return graph[start][node]
                elif node not in visited:
                    visited.add(node)
                    v = DFS(node,end)
                    if v != -1:
                        return graph[start][node] * v
            return -1

        # solve_answer
        ans = []
        for start,end in queries:
            visited = set()
            ans.append(DFS(start,end))
        return ans

12.5 【DFS】【拓扑排序】课程表

题目地址：https://leetcode.cn/problems/course-schedule/description/?envType=study-plan-v2&envId=top-interview-150

  该题就是考察判断一个有向无环图内是否有环，但是这里要多加一步，判断目前的课程是否曾经被访问过，否则会超时。

class Solution:
    def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
        graph = {}
        history_visited = set()

        # graph_construction
        for x,y in prerequisites:
            if y in graph:
                graph[y].add(x)
            else:
                graph[y] = {x}
        
        def DFS(node):
            if node in visited:
                return False
            if node in history_visited:
                return True
            visited.add(node)
            history_visited.add(node)
            if node in graph:
                for n in graph[node]:
                    if not DFS(n):
                        return False
            visited.remove(node)
            return True
        
        for i in range(numCourses):
            if i in history_visited:
                continue
            visited = set()
            if not DFS(i):
                return False
        return True

12.6 【DFS】【拓扑排序】课程表 II

题目地址：https://leetcode.cn/problems/course-schedule-ii/description/?envType=study-plan-v2&envId=top-interview-150

  在上一题的基础上保留访问到的课程即可，最后倒序输出。

class Solution:
    def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:
        graph = {}
        history_visited = set()
        ans = []

        # graph_construction
        for x,y in prerequisites:
            if y in graph:
                graph[y].add(x)
            else:
                graph[y] = {x}
        
        def DFS(node):
            if node in visited:
                return False
            if node in history_visited:
                return True
            visited.add(node)
            history_visited.add(node)
            if node in graph:
                for n in graph[node]:
                    if not DFS(n):
                        return False
            visited.remove(node)
            ans.append(node)
            return True
        
        for i in range(numCourses):
            if i in history_visited:
                continue
            visited = set()
            if not DFS(i):
                return []
        return ans[::-1]

13 图的广度优先搜索

13.1 【BFS】蛇梯棋

题目地址：https://leetcode.cn/problems/snakes-and-ladders/description/?envType=study-plan-v2&envId=top-interview-150

  利用广度优先遍历找到最快到达终点的那条路径，同时需要记录走的步数和已经访问过的结点，难点在于如何表示图中坐标。

class Solution:
    def snakesAndLadders(self, board: List[List[int]]) -> int:
        n = len(board)
        visited = set()
        stack = [1]
        ans = 1

        # index
        def position(num):
            i = (num-1)//n
            x = n-1-i
            if i%2:
                y = n-1-(num-1)%n
            else:
                y = (num-1)%n
            return x,y

        while stack:
            cur_idx = []
            for idx in stack:
                for nxt in range(idx+1,min(idx+6,n*n)+1):
                    if nxt not in visited:
                        visited.add(nxt)
                        x,y = position(nxt)
                        if board[x][y] != -1:
                            nxt = board[x][y]
                        cur_idx.append(nxt)
                        if nxt == n*n:
                            return ans
            ans += 1
            stack = cur_idx
        return -1

13.2 【BFS】最小基因变化

题目地址：https://leetcode.cn/problems/minimum-genetic-mutation/description/?envType=study-plan-v2&envId=top-interview-150

  从基因的每个字母出发，找到存在于$bank$中的下一步修改，然后进行广度优先遍历，最后判断是否有一次修改可以变为$endGene$。

class Solution:
    def minMutation(self, startGene: str, endGene: str, bank: List[str]) -> int:
        if endGene not in bank:
            return -1
        
        stack = [startGene]
        visited = set()
        step = 1

        while stack:
            cur = []
            for gene in stack:
                for i in range(8):
                    for s in ['A','C','G','T']:
                        if gene[i] != s:
                            tmp = list(gene)
                            tmp[i] = s
                            tmp = ''.join(tmp)
                            if tmp in bank and tmp not in visited:
                                visited.add(tmp)
                                cur.append(tmp)
                                if tmp == endGene:
                                    return step
            step += 1
            stack = cur
        return -1

13.3 【双向BFS】单词接龙

题目地址：https://leetcode.cn/problems/word-ladder/description/?envType=study-plan-v2&envId=top-interview-150

  这道题采用$BFS$会超时，所以要从$beginWord$和$endWord$分别开始进行$BFS$，最后实现一个双向$BFS$来优化时间复杂度。

class Solution:
    def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:
        if endWord not in wordList:
            return 0

        # word_single_set
        word_list = set()
        for word in wordList:
            for i in range(len(word)):
                word_list.add(word[i])
        word_list = list(word_list)

        left,right = [beginWord],[endWord]
        visited = set()
        step = 1

        while left:
            cur = []
            for word in left:
                for i in range(len(word)):
                    for s in word_list:
                        if word[i] != s: