DFS, or Depth First Search, is a traversal algorithm used to explore graphs and trees. It starts from the root and explores each branch as far as possible before backtracking. This algorithm can be used to perform tree traversal in pre-order, in-order, and post-order. Often, the Stack data structure is used for DFS traversal.
BFS stands for Breadth-First Search, which is also known as level order traversal. As the name suggests, after traversing all the nodes in the current level, it will move on to the next level. Usually, the Queue data structure is used for the BFS traversal.
You can get a clear view of how DFS and BFS traverse a tree through the graph below:
Below is a list of practice problems from Leetcode about DFS and BFS. Happy coding!😄
• DFS
https://leetcode.com/problems/sum-root-to-leaf-numbers/
class Solution:
def sumNumbers(self, root: Optional[TreeNode]) -> int:
def dfs(node, num):
if node is None:
return 0
num = num * 10 + node.val
if node.left == None and node.right == None:
return num
return dfs(node.left, num) + dfs(node.right, num)
return dfs(root, 0)
https://leetcode.com/problems/path-sum-ii/
class Solution:
def pathSum(self, root: Optional[TreeNode], targetSum: int) -> List[List[int]]:
ans = []
def dfs(node, curSum, cur):
if node == None:
return
cur.append(node.val)
curSum += node.val
if node.left == None and node.right == None and curSum == targetSum:
ans.append(cur.copy())
dfs(node.left, curSum, cur)
dfs(node.right, curSum, cur)
cur.pop()
dfs(root, 0, [])
return ans
https://leetcode.com/problems/path-sum-iii/
class Solution:
def pathSum(self, root: Optional[TreeNode], targetSum: int) -> int:
self.ans = 0
lookup = {}
def dfs(node, curSum):
if node == None:
return
curSum += node.val
if curSum == targetSum:
self.ans += 1
if curSum - targetSum in lookup:
self.ans += lookup[curSum - targetSum]
lookup[curSum] = lookup.get(curSum, 0) + 1
dfs(node.left, curSum)
dfs(node.right, curSum)
lookup[curSum] -= 1
dfs(root, 0)
return self.ans
https://leetcode.com/problems/binary-tree-paths/
class Solution:
def binaryTreePaths(self, root: Optional[TreeNode]) -> List[str]:
ans = []
def dfs(node, temp):
if node is None:
return []
if node.left == None and node.right == None:
return ans.append(temp + str(node.val))
temp += str(node.val) + "->"
dfs(node.left, temp)
dfs(node.right, temp)
dfs(root, "")
return ans
https://leetcode.com/problems/smallest-string-starting-from-leaf/
class Solution:
def smallestFromLeaf(self, root: Optional[TreeNode]) -> str:
self.ans = 'z' + chr(1)
def dfs(node, s):
if node == None:
return
s += chr(ord('a') + node.val)
if node.left == None and node.right == None:
self.ans = min(self.ans, s[::-1])
dfs(node.left, s)
dfs(node.right, s)
s = s[:-1]
dfs(root, "")
return self.ans
https://leetcode.com/problems/diameter-of-binary-tree/
class Solution:
def diameterOfBinaryTree(self, root: Optional[TreeNode]) -> int:
self.ans = 0
def dfs(root):
if root == None:
return 0
l, r = dfs(root.left), dfs(root.right)
self.ans = max((l + r), self.ans)
return max(l, r) + 1
dfs(root)
return self.ans
https://leetcode.com/problems/binary-tree-maximum-path-sum/
class Solution:
def maxPathSum(self, root: Optional[TreeNode]) -> int:
self.ans = float('-inf')
def dfs(node):
if node == None:
return 0
l, r = dfs(node.left), dfs(node.right)
self.ans = max(self.ans, l + r + node.val)
return max(0, max(l, r) + node.val)
dfs(root)
return self.ans
https://leetcode.com/problems/longest-univalue-path/
class Solution:
def longestUnivaluePath(self, root: Optional[TreeNode]) -> int:
self.ans = 0
def dfs(node):
if node == None:
return 0
l, r = dfs(node.left), dfs(node.right)
L, R = 0, 0
if node.left != None and node.left.val == node.val:
L = l
if node.right != None and node.right.val == node.val:
R = r
self.ans = max(self.ans, L + R)
return max(L, R) + 1
dfs(root)
return self.ans
https://leetcode.com/problems/n-ary-tree-preorder-traversal/
class Solution:
def preorder(self, root: 'Node') -> List[int]:
self.ans = []
def dfs(node):
if node == None:
return
self.ans.append(node.val)
for child in node.children:
dfs(child)
dfs(root)
return self.ans
https://leetcode.com/problems/n-ary-tree-postorder-traversal/
class Solution:
def postorder(self, root: 'Node') -> List[int]:
self.ans = []
def dfs(node):
if node == None:
return
for child in node.children:
dfs(child)
self.ans.append(node.val)
dfs(root)
return self.ans
https://leetcode.com/problems/minimum-depth-of-binary-tree/
class Solution:
def minDepth(self, root: Optional[TreeNode]) -> int:
self.ans = float("inf")
if root == None:
return 0
def dfs(node, dep):
if node == None:
return 0
if node.left == None and node.right == None:
self.ans = min(self.ans, dep)
dfs(node.left, dep + 1)
dfs(node.right, dep + 1)
dfs(root, 1)
return self.ans
https://leetcode.com/problems/balanced-binary-tree/
class Solution:
def isBalanced(self, root: Optional[TreeNode]) -> bool:
def dfs(node):
if node == None:
return 0
l, r = dfs(node.left), dfs(node.right)
if l == -1:
return -1
if r == -1:
return -1
if abs(l - r) > 1:
return -1
return max(l, r) + 1
return dfs(root) != -1
https://leetcode.com/problems/increasing-order-search-tree/
class Solution:
def increasingBST(self, root: TreeNode) -> TreeNode:
dummy = TreeNode(-1)
self.cur = dummy
def dfs(node):
if node == None:
return
dfs(node.left)
self.cur.right = node
node.left = None
self.cur = self.cur.right
dfs(node.right)
dfs(root)
return dummy.right
https://leetcode.com/problems/sum-of-left-leaves/
class Solution:
def sumOfLeftLeaves(self, root: Optional[TreeNode]) -> int:
self.ans = 0
def dfs(node):
if node == None:
return 0
if node.left != None and node.left.left == None and node.left.right == None:
self.ans += node.left.val
dfs(node.left)
dfs(node.right)
dfs(root)
return self.ans
https://leetcode.com/problems/binary-tree-pruning/
class Solution:
def pruneTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
def dfs(node):
if not node:
return False
l, r = dfs(node.left), dfs(node.right)
if not l:
node.left = None
if not r:
node.right = None
return l or r or node.val == 1
return root if dfs(root) else None
https://leetcode.com/problems/binary-tree-longest-consecutive-sequence/
class Solution:
def longestConsecutive(self, root: Optional[TreeNode]) -> int:
self.max = 1
def dfs(node, cnt):
self.max = max(self.max, cnt)
if node.left:
if node.left.val == node.val + 1:
dfs(node.left, cnt + 1)
else:
dfs(node.left, 1)
if node.right:
if node.right.val == node.val + 1:
dfs(node.right, cnt + 1)
else:
dfs(node.right, 1)
dfs(root, 1)
return self.max
https://leetcode.com/problems/binary-tree-longest-consecutive-sequence-ii/
class Solution:
def longestConsecutive(self, root: Optional[TreeNode]) -> int:
self.max = 0
def dfs(node):
if node == None:
return [0, 0]
l, r = dfs(node.left), dfs(node.right)
inc, dec = 1, 1
if node.left:
if node.val == node.left.val + 1:
dec = l[1] + 1
if node.val == node.left.val - 1:
inc = l[0] + 1
if node.right:
if node.val == node.right.val + 1:
dec = max(dec, r[1] + 1)
if node.val == node.right.val - 1:
inc = max(inc, r[0] + 1)
self.max = max(self.max, inc + dec - 1)
return [inc, dec]
dfs(root)
return self.max
https://leetcode.com/problems/maximum-width-of-binary-tree/
class Solution:
def widthOfBinaryTree(self, root: Optional[TreeNode]) -> int:
self.max = 0
pos = []
def dfs(node, dep, p):
if node == None:
return
if dep == len(pos):
pos.append(p)
self.max = max(self.max, p - pos[dep] + 1)
dfs(node.left, dep + 1, p * 2 + 1)
dfs(node.right, dep + 1, p * 2 + 2)
dfs(root, 0, 0)
return self.max
https://leetcode.com/problems/maximum-product-of-splitted-binary-tree/
class Solution:
def maxProduct(self, root: Optional[TreeNode]) -> int:
self.total = 0
self.ans = 0
def dfs1(node):
if node == None:
return
self.total += node.val
dfs1(node.left)
dfs1(node.right)
def dfs2(node):
if node == None:
return 0
l, r = dfs2(node.left), dfs2(node.right)
self.ans = max(self.ans, max(l * (self.total - l), r * (self.total - r)))
return node.val + l + r
dfs1(root)
dfs2(root)
return self.ans % (10 ** 9 + 7)
https://leetcode.com/problems/find-mode-in-binary-search-tree/
class Solution:
def findMode(self, root: Optional[TreeNode]) -> List[int]:
self.pre = root.val
self.cur, self.max = 0, 0
self.ans = []
def dfs(node):
if node == None:
return
dfs(node.left)
if node.val != self.pre:
self.cur = 1
self.pre = node.val
else:
self.cur += 1
if self.cur > self.max:
self.max = self.cur
self.ans.clear()
self.ans.append(node.val)
elif self.cur == self.max:
self.ans.append(node.val)
dfs(node.right)
dfs(root)
return self.ans
https://leetcode.com/problems/convert-sorted-array-to-binary-search-tree/
class Solution:
def sortedArrayToBST(self, nums: List[int]) -> Optional[TreeNode]:
def dfs(left, right):
if left > right:
return None
mid = (left + right) // 2
root = TreeNode(nums[mid])
root.left = dfs(left, mid - 1)
root.right = dfs(mid + 1, right)
return root
return dfs(0, len(nums) - 1)
https://leetcode.com/problems/kth-smallest-element-in-a-bst/
class Solution:
def kthSmallest(self, root: Optional[TreeNode], k: int) -> int:
self.ans = None
self.k = k
def dfs(node):
if node is None:
return
dfs(node.left)
self.k -= 1
if self.k == 0:
self.ans = node.val
return
dfs(node.right)
dfs(root)
return self.ans
https://leetcode.com/problems/recover-binary-search-tree/
class Solution:
def recoverTree(self, root: Optional[TreeNode]) -> None:
arr = []
def dfs(node):
if node == None:
return
dfs(node.left)
arr.append(node)
dfs(node.right)
dfs(root)
a = None
b = None
for i in range(0, len(arr)):
if arr[i].val > arr[i + 1].val:
a = arr[i]
break
for i in range(len(arr) - 1, -1, -1):
if arr[i].val < arr[i - 1].val:
b = arr[i]
break
a.val, b.val = b.val, a.val
https://leetcode.com/problems/inorder-successor-in-bst/
class Solution:
def inorderSuccessor(self, root: TreeNode, p: TreeNode) -> Optional[TreeNode]:
self.ans = None
self.flag = False
def dfs(node):
if node == None:
return
dfs(node.left)
if self.flag and self.ans == None:
self.ans = node
if not self.flag and node == p:
self.flag = True
dfs(node.right)
dfs(root)
return self.ans
https://leetcode.com/problems/closest-binary-search-tree-value-ii/
class Solution:
def closestKValues(self, root: Optional[TreeNode], target: float, k: int) -> List[int]:
self.q = deque()
def dfs(node):
if node == None:
return
dfs(node.left)
if len(self.q) < k:
self.q.append(node.val)
elif abs(self.q[0] - target) > abs(node.val - target):
self.q.popleft()
self.q.append(node.val)
dfs(node.right)
dfs(root)
return self.q
https://leetcode.com/problems/generate-parentheses/
class Solution:
def generateParenthesis(self, n: int) -> List[str]:
def dfs(u, l, r, cur):
if u == 2 * n:
return ans.append(cur)
if r < l: dfs(u + 1, l, r + 1, cur + ")")
if l < n: dfs(u + 1, l + 1, r, cur + "(")
ans = []
dfs(0, 0, 0, "")
return ans
https://leetcode.com/problems/throne-inheritance/
class ThroneInheritance:
def __init__(self, kingName: str):
self.g = defaultdict(list)
self.kingName = kingName
self.dead = set()
def birth(self, parentName: str, childName: str) -> None:
self.g[parentName].append(childName)
def death(self, name: str) -> None:
self.dead.add(name)
def getInheritanceOrder(self) -> List[str]:
def dfs(u):
if u not in self.dead:
ans.append(u)
for v in self.g[u]:
dfs(v)
ans = []
dfs(self.kingName)
return ans
https://leetcode.com/problems/number-of-enclaves/
class Solution:
def numEnclaves(self, grid: List[List[int]]) -> int:
def dfs(i, j):
grid[i][j] = 0
for ni, nj in [(i - 1, j), (i + 1, j), (i, j - 1), (i, j + 1)]:
if 0 <= ni < m and 0 <= nj < n and grid[ni][nj] == 1:
dfs(ni, nj)
m, n = len(grid), len(grid[0])
for i in range(m):
for j in range(n):
if grid[i][j] == 1 and (i == 0 or j == 0 or i == m - 1 or j == n - 1):
dfs(i, j)
return sum(sum(row) for row in grid)
https://leetcode.com/problems/validate-binary-tree-nodes/
class Solution:
def validateBinaryTreeNodes(self, n: int, leftChild: List[int], rightChild: List[int]) -> bool:
def dfs(u):
vis.add(u)
if leftChild[u] != -1:
if leftChild[u] in vis or not dfs(leftChild[u]):
return False
if rightChild[u] != -1:
if rightChild[u] in vis or not dfs(rightChild[u]):
return False
return True
d = [0] * n
for x in leftChild + rightChild:
if x != -1:
d[x] += 1
if d[x] > 1:
return False
if d.count(0) != 1:
return False
root = d.index(0)
vis = set()
if not dfs(root):
return False
return len(vis) == n
https://leetcode.com/problems/number-of-islands/
class Solution:
def numIslands(self, grid: List[List[str]]) -> int:
def dfs(i, j):
grid[i][j] = '0'
for ni, nj in [(i - 1, j), (i + 1, j), (i, j - 1), (i, j + 1)]:
if 0 <= ni < m and 0 <= nj < n and grid[ni][nj] == '1':
dfs(ni, nj)
ans = 0
m, n = len(grid), len(grid[0])
for i in range(m):
for j in range(n):
if grid[i][j] == '1':
ans += 1
dfs(i, j)
return ans
https://leetcode.com/problems/count-sub-islands/
class Solution:
def countSubIslands(self, grid1: List[List[int]], grid2: List[List[int]]) -> int:
def dfs(i, j):
nonlocal isSub
grid2[i][j] = 0
if grid1[i][j] == 0:
isSub = False
for ni, nj in [(i - 1, j), (i + 1, j), (i, j - 1), (i, j + 1)]:
if 0 <= ni < m and 0 <= nj < n and grid2[ni][nj] == 1:
dfs(ni, nj)
ans = 0
m, n = len(grid1), len(grid1[0])
for i in range(m):
for j in range(n):
if grid2[i][j] == 1:
isSub = True
dfs(i, j)
if isSub:
ans += 1
return ans
https://leetcode.com/problems/count-servers-that-communicate/
class Solution:
def countServers(self, grid: List[List[int]]) -> int:
def dfs(i, j):
nonlocal cnt
cnt += 1
vis.add((i, j))
for ni, nj in g1[i] + g2[j]:
if (ni, nj) not in vis:
dfs(ni, nj)
g1 = defaultdict(list)
g2 = defaultdict(list)
m, n = len(grid), len(grid[0])
for i in range(m):
for j in range(n):
if grid[i][j] == 1:
g1[i].append([i, j])
g2[j].append([i, j])
vis = set()
ans = 0
for i in range(m):
for j in range(n):
if grid[i][j] == 1 and (i, j) not in vis:
cnt = 0
dfs(i, j)
if cnt > 1:
ans += cnt
return ans
https://leetcode.com/problems/word-search/
class Solution:
def exist(self, board: List[List[str]], word: str) -> bool:
def dfs(i, j, u):
if board[i][j] != word[u]: return False
if u == len(word) - 1: return True
t = board[i][j]
board[i][j] = '#'
for ni, nj in [(i - 1, j), (i + 1, j), (i, j - 1), (i, j + 1)]:
if 0 <= ni < m and 0 <= nj < n and board[ni][nj] != '#':
if dfs(ni, nj, u + 1): return True
board[i][j] = t
return False
m, n = len(board), len(board[0])
for i in range(m):
for j in range(n):
if dfs(i, j, 0): return True
return False
https://leetcode.com/problems/surrounded-regions/
class Solution:
def solve(self, board: List[List[str]]) -> None:
def dfs(i, j):
board[i][j] = '#'
for ni, nj in [(i - 1, j), (i + 1, j), (i, j - 1), (i, j + 1)]:
if 0 <= ni < m and 0 <= nj < n and board[ni][nj] == 'O':
dfs(ni, nj)
m, n = len(board), len(board[0])
for i in range(m):
for j in range(n):
if (i == 0 or j == 0 or i == m - 1 or j == n - 1) and board[i][j] == 'O':
dfs(i, j)
for i in range(m):
for j in range(n):
if board[i][j] == '#': board[i][j] = 'O'
elif board[i][j] == 'O': board[i][j] = 'X'
https://leetcode.com/problems/clone-graph/
class Solution:
def cloneGraph(self, node: 'Node') -> 'Node':
def dfs(node):
if node is None:
return None
if node not in d:
d[node] = Node(node.val)
for v in node.neighbors:
d[node].neighbors.append(dfs(v))
return d[node]
d = {}
return dfs(node)
https://leetcode.com/problems/number-of-connected-components-in-an-undirected-graph/
class Solution:
def countComponents(self, n: int, edges: List[List[int]]) -> int:
def dfs(u):
vis.add(u)
for v in g[u]:
if v not in vis:
dfs(v)
ans = 0
g = defaultdict(list)
vis = set()
for u, v in edges:
g[u].append(v)
g[v].append(u)
for i in range(n):
if i not in vis:
ans += 1
dfs(i)
return ans
https://leetcode.com/problems/pacific-atlantic-water-flow/
class Solution:
def pacificAtlantic(self, heights: List[List[int]]) -> List[List[int]]:
def dfs(i, j, h):
h.add((i, j))
for ni, nj in [(i - 1, j), (i + 1, j), (i, j - 1), (i, j + 1)]:
if 0 <= ni < m and 0 <= nj < n and heights[ni][nj] >= heights[i][j] and (ni, nj) not in h:
dfs(ni, nj, h)
m, n = len(heights), len(heights[0])
h1, h2 = set(), set()
for i in range(m):
for j in range(n):
if i == 0 or j == 0: dfs(i, j, h1)
if i == m - 1 or j == n - 1: dfs(i, j, h2)
return list(h1 & h2)
https://leetcode.com/problems/the-maze/
class Solution:
def hasPath(self, maze: List[List[int]], start: List[int], destination: List[int]) -> bool:
def dfs(i, j):
if [i, j] == destination:
return True
vis.add((i, j))
for d in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
ni, nj = i, j
while 0 <= ni + d[0] < m and 0 <= nj + d[1] < n and maze[ni + d[0]][nj + d[1]] == 0:
ni, nj = ni + d[0], nj + d[1]
if (ni, nj) not in vis and dfs(ni, nj):
return True
return False
m, n = len(maze), len(maze[0])
vis = set()
return dfs(start[0], start[1])
https://leetcode.com/problems/number-of-distinct-islands/
class Solution:
def numDistinctIslands(self, grid: List[List[int]]) -> int:
def dfs(i, j):
nonlocal path
grid[i][j] = 0
for ni, nj, d in [(i - 1, j, 'u'), (i + 1, j, 'd'), (i, j - 1, 'l'), (i, j + 1, 'r')]:
path += d
if 0 <= ni < m and 0 <= nj < n and grid[ni][nj] == 1:
dfs(ni, nj)
m, n = len(grid), len(grid[0])
ans = set()
for i in range(m):
for j in range(n):
if grid[i][j] == 1:
path = ''
dfs(i, j)
ans.add(path)
return len(ans)
https://leetcode.com/problems/max-area-of-island/
class Solution:
def maxAreaOfIsland(self, grid: List[List[int]]) -> int:
def dfs(i, j):
nonlocal cnt
grid[i][j] = 0
cnt += 1
for ni, nj in [(i - 1, j), (i + 1, j), (i, j - 1), (i, j + 1)]:
if 0 <= ni < m and 0 <= nj < n and grid[ni][nj] == 1:
dfs(ni, nj)
ans = 0
m, n = len(grid), len(grid[0])
for i in range(m):
for j in range(n):
if grid[i][j] == 1:
cnt = 0
dfs(i, j)
ans = max(cnt, ans)
return ans
https://leetcode.com/problems/keys-and-rooms/
class Solution:
def canVisitAllRooms(self, rooms: List[List[int]]) -> bool:
def dfs(u):
vis.add(u)
for v in rooms[u]:
if v not in vis:
dfs(v)
vis = set()
dfs(0)
return len(vis) == len(rooms)
https://leetcode.com/problems/nested-list-weight-sum/
class Solution:
def depthSum(self, nestedList: List[NestedInteger]) -> int:
def dfs(cur, dep):
nonlocal ans
for x in cur:
if x.isInteger():
ans += dep * x.getInteger()
else:
dfs(x.getList(), dep + 1)
ans = 0
dfs(nestedList, 1)
return ans
https://leetcode.com/problems/employee-importance/
class Solution:
def getImportance(self, employees: List['Employee'], id: int) -> int:
def dfs(u):
nonlocal ans
ans += d[u].importance
for v in d[u].subordinates:
dfs(v)
ans = 0
d = {}
for e in employees:
d[e.id] = e
dfs(id)
return ans
https://leetcode.com/problems/all-paths-from-source-to-target/
class Solution:
def allPathsSourceTarget(self, graph: List[List[int]]) -> List[List[int]]:
def dfs(u, path):
nonlocal ans
path.append(u)
if u == len(graph) - 1:
ans.append(path[::])
for v in graph[u]:
dfs(v, path)
path.pop()
ans = []
dfs(0, [])
return ans
https://leetcode.com/problems/jump-game-iii/
class Solution:
def canReach(self, arr: List[int], start: int) -> bool:
def dfs(i):
if arr[i] == 0:
return True
vis.add(i)
ans = False
if i + arr[i] < len(arr) and i + arr[i] not in vis:
ans |= dfs(i + arr[i])
if i - arr[i] >= 0 and i - arr[i] not in vis:
ans |= dfs(i - arr[i])
return ans
vis = set()
return dfs(start)
https://leetcode.com/problems/number-of-closed-islands/
class Solution:
def closedIsland(self, grid: List[List[int]]) -> int:
def dfs(i, j):
grid[i][j] = 1
for ni, nj in [(i - 1, j), (i + 1, j), (i, j - 1), (i, j + 1)]:
if 0 <= ni < m and 0 <= nj < n and grid[ni][nj] == 0:
dfs(ni, nj)
m, n = len(grid), len(grid[0])
for i in range(m):
for j in range(n):
if (i == 0 or j == 0 or i == m - 1 or j == n - 1) and grid[i][j] == 0:
dfs(i, j)
ans = 0
for i in range(m):
for j in range(n):
if grid[i][j] == 0:
ans += 1
dfs(i, j)
return ans
https://leetcode.com/problems/reorder-routes-to-make-all-paths-lead-to-the-city-zero/
class Solution:
def minReorder(self, n: int, connections: List[List[int]]) -> int:
def dfs(u):
nonlocal ans
vis.add(u)
for v in g[u]:
if v not in vis:
if (u, v) not in origin:
ans += 1
dfs(v)
origin = set((u, v) for u, v in connections)
g = defaultdict(list)
for u, v in connections:
g[u].append(v)
g[v].append(u)
ans = 0
vis = set()
dfs(0)
return len(connections) - ans
https://leetcode.com/problems/number-of-operations-to-make-network-connected/
class Solution:
def makeConnected(self, n: int, connections: List[List[int]]) -> int:
def dfs(u):
vis.add(u)
for v in g[u]:
if v not in vis:
dfs(v)
if len(connections) < n - 1:
return -1
g = defaultdict(list)
for u, v in connections:
g[u].append(v)
g[v].append(u)
ans = 0
vis = set()
for i in range(n):
if i not in vis:
ans += 1
dfs(i)
return ans - 1
https://leetcode.com/problems/possible-bipartition/
class Solution:
def possibleBipartition(self, n: int, dislikes: List[List[int]]) -> bool:
def dfs(u, c):
if u in color:
return color[u] == c
color[u] = c
for v in g[u]:
if not dfs(v, c ^ 1):
return False
return True
color = {}
g = defaultdict(list)
for u, v in dislikes:
g[u].append(v)
g[v].append(u)
for i in range(1, n + 1):
if i not in color and not dfs(i, 0):
return False
return True
https://leetcode.com/problems/kill-process/
class Solution:
def killProcess(self, pid: List[int], ppid: List[int], kill: int) -> List[int]:
def dfs(u):
ans.append(u)
for v in g[u]:
dfs(v)
n = len(pid)
g = defaultdict(list)
for i in range(n):
g[ppid[i]].append(pid[i])
ans = []
dfs(kill)
return ans
https://leetcode.com/problems/time-needed-to-inform-all-employees/
class Solution:
def numOfMinutes(self, n: int, headID: int, manager: List[int], informTime: List[int]) -> int:
def dfs(u, time):
nonlocal ans
ans = max(ans, time)
for v in g[u]:
dfs(v, time + informTime[u])
ans = 0
g = defaultdict(list)
for i in range(n):
g[manager[i]].append(i)
dfs(headID, 0)
return ans
https://leetcode.com/problems/lexicographical-numbers/
class Solution:
def lexicalOrder(self, n: int) -> List[int]:
def dfs(u):
for i in range(1 if u == 0 else 0, min(9, n) + 1):
if u + i <= n:
ans.append(u + i)
if (u + i) * 10 <= n:
dfs((u + i) * 10)
ans = []
dfs(0)
return ans
https://leetcode.com/problems/most-stones-removed-with-same-row-or-column/
class Solution:
def removeStones(self, stones: List[List[int]]) -> int:
def dfs(r, c):
vis.add((r, c))
for nr, nc in g1[r] + g2[c]:
if (nr, nc) not in vis:
dfs(nr, nc)
g1 = defaultdict(list)
g2 = defaultdict(list)
for r, c in stones:
g1[r].append([r, c])
g2[c].append([r, c])
ans = 0
vis = set()
for r, c in stones:
if (r, c) not in vis:
ans += 1
dfs(r, c)
return len(stones) - ans
https://leetcode.com/problems/sentence-similarity-ii/
class Solution:
def areSentencesSimilarTwo(self, sentence1: List[str], sentence2: List[str], similarPairs: List[List[str]]) -> bool:
def dfs(u, target):
if u == target:
return True
vis.add(u)
for v in g[u]:
if v not in vis and dfs(v, target):
return True
return False
if len(sentence1) != len(sentence2):
return False
g = defaultdict(list)
for u, v in similarPairs:
g[u].append(v)
g[v].append(u)
for u, v in zip(sentence1, sentence2):
vis = set()
if not dfs(u, v):
return False
return True
https://leetcode.com/problems/evaluate-division/
class Solution:
def calcEquation(self, equations: List[List[str]], values: List[float], queries: List[List[str]]) -> List[float]:
def dfs(x, y, i, cur):
if x == y:
ans[i] = cur
return
vis.add(x)
for z, val in g[x]:
if z not in vis:
dfs(z, y, i, cur * val)
g = defaultdict(list)
for (x, y), z in zip(equations, values):
g[x].append((y, z))
g[y].append((x, 1/z))
ans = [-1] * len(queries)
for i, (x, y) in enumerate(queries):
vis = set()
if x in g and y in g:
dfs(x, y, i, 1)
return ans
https://leetcode.com/problems/letter-combinations-of-a-phone-number/
class Solution:
def letterCombinations(self, digits: str) -> List[str]:
if digits == "":
return []
d = {
"2": "abc",
"3": "def",
"4": "ghi",
"5": "jkl",
"6": "mno",
"7": "pqrs",
"8": "tuv",
"9": "wxyz"
}
ans = []
def dfs(cur, j):
if j == len(digits):
return ans.append(cur)
for v in d[digits[j]]:
dfs(cur + str(v), j + 1)
dfs("", 0)
return ans
https://leetcode.com/problems/unique-paths-iii/
class Solution:
def uniquePathsIII(self, grid: List[List[int]]) -> int:
def dfs(i, j):
nonlocal ans
if i == er and j == ec:
if len(vis) + 1 == m * n - block:
ans += 1
return
vis.add((i, j))
for ni, nj in [(i - 1, j), (i + 1, j), (i, j - 1), (i, j + 1)]:
if 0 <= ni < m and 0 <= nj < n and grid[ni][nj] != -1 and (ni, nj) not in vis:
dfs(ni, nj)
vis.remove((i, j))
ans = 0
vis = set()
block = 0
sr, sc, er, ec = 0, 0, 0, 0
m, n = len(grid), len(grid[0])
for i in range(m):
for j in range(n):
if grid[i][j] == 1:
sr, sc = i, j
if grid[i][j] == 2:
er, ec = i, j
if grid[i][j] == -1:
block += 1
dfs(sr, sc)
return ans
https://leetcode.com/problems/is-graph-bipartite/
class Solution:
def isBipartite(self, graph: List[List[int]]) -> bool:
def dfs(u, c):
if u in vis:
return vis[u] == c
vis[u] = c
for v in graph[u]:
if not dfs(v, c ^ 1):
return False
return True
vis = {}
n = len(graph)
for i in range(n):
if i not in vis:
if not dfs(i, 0):
return False
return True
https://leetcode.com/problems/coloring-a-border/
class Solution:
def colorBorder(self, grid: List[List[int]], row: int, col: int, color: int) -> List[List[int]]:
def dfs(i, j):
t[i][j] = True
grid[i][j] = color
for ni, nj in [(i - 1, j), (i + 1, j), (i, j - 1), (i, j + 1)]:
if 0 <= ni < m and 0 <= nj < n and grid[ni][nj] == old:
dfs(ni, nj)
if grid[row][col] == color:
return grid
m, n = len(grid), len(grid[0])
old = grid[row][col]
t = [[False] * n for _ in range(m)]
dfs(row, col)
for i in range(1, m - 1):
for j in range(1, n - 1):
if t[i][j] and t[i - 1][j] and t[i + 1][j] and t[i][j - 1] and t[i][j + 1]:
grid[i][j] = old
return grid
https://leetcode.com/problems/detect-cycles-in-2d-grid/
class Solution:
def containsCycle(self, grid: List[List[str]]) -> bool:
def dfs(i, j, pi, pj):
vis.add((i, j))
for ni, nj in [(i-1, j), (i + 1, j), (i, j - 1), (i, j + 1)]:
if 0 <= ni < m and 0 <= nj < n and grid[ni][nj] == grid[i][j] and (ni, nj) != (pi, pj):
if (ni, nj) in vis or dfs(ni, nj, i, j):
return True
return False
m, n = len(grid), len(grid[0])
vis = set()
for i in range(m):
for j in range(n):
if (i, j) not in vis:
if dfs(i, j, -1, -1):
return True
return False
https://leetcode.com/problems/shortest-bridge/
class Solution:
def shortestBridge(self, grid: List[List[int]]) -> int:
def dfs(i, j):
heapq.heappush(q, (0, i, j))
vis.add((i, j))
for ni, nj in [(i - 1, j), (i + 1, j), (i, j - 1), (i, j + 1)]:
if 0 <= ni < m and 0 <= nj < n and grid[ni][nj] == 1 and (ni, nj) not in vis:
dfs(ni, nj)
def bfs():
while q:
x, i, j = heapq.heappop(q)
if x > 0 and grid[i][j] == 1:
return x - 1
for ni, nj in [(i - 1, j), (i + 1, j), (i, j - 1), (i, j + 1)]:
if 0 <= ni < m and 0 <= nj < n and (ni, nj) not in vis:
vis.add((ni, nj))
heapq.heappush(q, (x + 1, ni, nj))
m, n = len(grid), len(grid[0])
q = []
for i in range(m):
for j in range(n):
if grid[i][j] == 1:
vis = set()
dfs(i, j)
return bfs()
https://leetcode.com/problems/minesweeper/
class Solution:
def updateBoard(self, board: List[List[str]], click: List[int]) -> List[List[str]]:
def dfs(i, j):
cnt = 0
for d in dirs:
ni, nj = i + d[0], j + d[1]
if 0 <= ni < m and 0 <= nj < n and board[ni][nj] == 'M':
cnt += 1
if cnt == 0:
board[i][j] = 'B'
for d in dirs:
ni, nj = i + d[0], j + d[1]
if 0 <= ni < m and 0 <= nj < n and board[ni][nj] == 'E':
dfs(ni, nj)
else:
board[i][j] = str(cnt)
dirs = [(-1, -1), (-1, 0), (-1, 1), (0, -1), (0, 1), (1, -1), (1, 0), (1, 1)]
m, n = len(board), len(board[0])
i, j = click
if board[i][j] == 'M':
board[i][j] = 'X'
else:
dfs(i, j)
return board
https://leetcode.com/problems/number-of-provinces/
class Solution:
def findCircleNum(self, isConnected: List[List[int]]) -> int:
def dfs(i):
vis.add(i)
for j in range(n):
if isConnected[i][j] and j not in vis:
dfs(j)
ans = 0
n = len(isConnected)
vis = set()
for i in range(n):
if i not in vis:
dfs(i)
ans += 1
return ans
https://leetcode.com/problems/all-paths-from-source-lead-to-destination/
class Solution:
def leadsToDestination(self, n: int, edges: List[List[int]], source: int, destination: int) -> bool:
@lru_cache(None)
def dfs(u):
if not g[u]:
return u == destination
vis.add(u)
for v in g[u]:
if v in vis or not dfs(v):
return False
vis.remove(u)
return True
vis = set()
g = defaultdict(list)
for u, v in edges:
g[u].append(v)
return dfs(source)
https://leetcode.com/problems/smallest-common-region/
class Solution:
def findSmallestRegion(self, regions: List[List[str]], region1: str, region2: str) -> str:
def dfs(u):
if u == region1 or u == region2:
return u
ans = set()
for v in g[u]:
t = dfs(v)
if t:
ans.add(t)
if len(ans) == 2:
return u
return ans.pop() if len(ans) == 1 else None
g = defaultdict(list)
sub = set()
for region in regions:
for i in range(1, len(region)):
g[region[0]].append(region[i])
sub.add(region[i])
for region in regions:
if region[0] not in sub:
return dfs(region[0])
https://leetcode.com/problems/regions-cut-by-slashes/
class Solution:
def regionsBySlashes(self, grid: List[str]) -> int:
def dfs(i, j):
g[i][j] = 1
for ni, nj in [(i - 1, j), (i + 1, j), (i, j - 1), (i, j + 1)]:
if 0 <= ni < m * 3 and 0 <= nj < n * 3 and g[ni][nj] == 0:
dfs(ni, nj)
m, n = len(grid), len(grid[0])
g = [[0] * n * 3 for _ in range(m * 3)]
for i in range(m):
for j in range(n):
if grid[i][j] == '/':
for k in range(3):
g[i * 3 + k][j * 3 + 2 - k] = 1
elif grid[i][j] == '\\':
for k in range(3):
g[i * 3 + k][j * 3 + k] = 1
ans = 0
for i in range(m * 3):
for j in range(n * 3):
if g[i][j] == 0:
ans += 1
dfs(i, j)
return ans
https://leetcode.com/problems/pyramid-transition-matrix/
class Solution:
def pyramidTransition(self, bottom: str, allowed: List[str]) -> bool:
@lru_cache(None)
def dfs(s, i):
if len(s) == 1:
return True
if i == len(s) - 1:
return dfs(s[:-1], 0)
for c in g[s[i: i + 2]]:
if dfs(s[:i] + c + s[i + 1:], i + 1):
return True
return False
g = defaultdict(list)
for s in allowed:
g[s[:2]].append(s[-1])
return dfs(bottom, 0)
https://leetcode.com/problems/loud-and-rich/
class Solution:
def loudAndRich(self, richer: List[List[int]], quiet: List[int]) -> List[int]:
@lru_cache(None)
def dfs(u):
if not g[u]:
return [quiet[u], u]
t = min(dfs(v) for v in g[u])
t = min(t, [quiet[u], u])
if quiet[ans[u]] > quiet[t[1]]:
ans[u] = t[1]
return t
n = len(quiet)
ans = list(range(n))
g = defaultdict(list)
for u, v in richer:
g[v].append(u)
for i in range(n):
dfs(i)
return ans
https://leetcode.com/problems/check-if-there-is-a-valid-path-in-a-grid/
class Solution:
def hasValidPath(self, grid: List[List[int]]) -> bool:
def dfs(i, j, d):
if i == m - 1 and j == n - 1:
return True
vis.add((i, j))
ni, nj = i + dirs[d][0], j + dirs[d][1]
if 0 <= ni < m and 0 <= nj < n and (ni, nj) not in vis and g[grid[ni][nj]][d] != -1:
if dfs(ni, nj, g[grid[ni][nj]][d]):
return True
return False
# 0 up 1 right 2 down 3 left
g = [[], [-1, 1, -1, 3], [0, -1, 2, -1], [3, 2, -1, -1], [1, -1, -1, 2], [-1, 0, 3, -1], [-1, -1, 1, 0]]
m, n = len(grid), len(grid[0])
vis = set()
dirs = [[-1, 0], [0, 1], [1, 0], [0, -1]]
for i in range(4):
if dfs(0, 0, i):
return True
return False
https://leetcode.com/problems/flower-planting-with-no-adjacent/
class Solution:
def gardenNoAdj(self, n: int, paths: List[List[int]]) -> List[int]:
ans = [0] * n
g = defaultdict(list)
for u, v in paths:
g[u - 1].append(v - 1)
g[v - 1].append(u - 1)
for i in range(n):
ans[i] = ({1, 2, 3, 4} - {ans[j] for j in g[i]}).pop()
return ans
https://leetcode.com/problems/nested-list-weight-sum-ii/
class Solution:
def depthSumInverse(self, nestedList: List[NestedInteger]) -> int:
def getDep(cur, u):
nonlocal mx
mx = max(mx, u)
for v in cur:
if not v.isInteger() and v.getList():
getDep(v.getList(), u + 1)
def dfs(cur, u):
nonlocal ans
for v in cur:
if v.isInteger():
ans += v.getInteger() * (mx - u + 1)
else:
dfs(v.getList(), u + 1)
mx = 0
getDep(nestedList, 1)
ans = 0
dfs(nestedList, 1)
return ans
• BFS
https://leetcode.com/problems/letter-combinations-of-a-phone-number/
class Solution:
def letterCombinations(self, digits: str) -> List[str]:
if digits == "":
return []
s = ["", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz" ]
a = [""]
for c in digits:
b = []
for cur in a:
for ch in s[int(c)]:
b.append(cur + ch)
a = b
return a
https://leetcode.com/problems/brace-expansion/
class Solution:
def expand(self, s: str) -> List[str]:
n = len(s)
a = ['']
i = 0
while i < n:
b = []
if s[i] == '{':
j = s.find('}', i)
t = [c for c in s[i + 1: j] if c.isalpha()]
i = j + 1
else:
t = s[i]
i = i + 1
for c in t:
for cur in a:
b.append(cur + c)
a = b
return sorted(a)
https://leetcode.com/problems/rotting-oranges/
class Solution:
def orangesRotting(self, grid: List[List[int]]) -> int:
q = deque()
m, n = len(grid), len(grid[0])
for i in range(m):
for j in range(n):
if grid[i][j] == 2:
q.append([i, j, 0])
time = 0
while q:
x, y, time = q.popleft()
for nx, ny in [(x - 1, y), (x + 1, y), (x, y - 1), (x, y + 1)]:
if 0 <= nx < m and 0 <= ny < n and grid[nx][ny] == 1:
grid[nx][ny] = 2
q.append([nx, ny, time + 1])
for g in grid:
if 1 in g:
return -1
return time
https://leetcode.com/problems/shortest-path-to-get-food/
class Solution:
def getFood(self, grid: List[List[str]]) -> int:
m, n = len(grid), len(grid[0])
vis = set()
q = deque()
for i in range(m):
for j in range(n):
if grid[i][j] == 'X':
vis.add((i, j))
elif grid[i][j] == '*':
vis.add((i, j))
q.append((i, j, 0))
while q:
i, j, k = q.popleft()
if grid[i][j] == '#':
return k
for ni, nj in [(i - 1, j), (i + 1, j), (i, j - 1), (i, j + 1)]:
if 0 <= ni < m and 0 <= nj < n and (ni, nj) not in vis:
vis.add((ni, nj))
q.append((ni, nj, k + 1))
return -1
https://leetcode.com/problems/minimum-knight-moves/
class Solution:
def minKnightMoves(self, x: int, y: int) -> int:
dirs = [[-2, 1], [-1, 2], [1, 2], [2, 1], [2, -1], [1, -2], [-1, -2], [-2, -1]]
q = deque()
vis = set()
q.append((0, 0, 0))
while q:
i, j, k = q.popleft()
if i == x and j == y:
return k
for a, b in dirs:
ni, nj = i + a, j + b
if (ni, nj) not in vis:
vis.add((ni, nj))
q.append((ni, nj, k + 1))
https://leetcode.com/problems/nearest-exit-from-entrance-in-maze/
class Solution:
def nearestExit(self, maze: List[List[str]], entrance: List[int]) -> int:
m, n = len(maze), len(maze[0])
q = deque()
q.append((entrance[0], entrance[1], 0))
vis = {(entrance[0], entrance[1])}
while q:
i, j, k = q.popleft()
if (i == 0 or j == 0 or i == m - 1 or j == n - 1) and [i, j] != entrance:
return k
for ni, nj in [(i - 1, j), (i + 1, j), (i, j - 1), (i, j + 1)]:
if 0 <= ni < m and 0 <= nj < n and (ni, nj) not in vis and maze[ni][nj] == '.':
q.append((ni, nj, k + 1))
vis.add((ni, nj))
return -1
https://leetcode.com/problems/minimum-operations-to-convert-number/
class Solution:
def minimumOperations(self, nums: List[int], start: int, goal: int) -> int:
q = deque()
q.append((start, 0))
vis = {start}
while q:
u, k = q.popleft()
if u == goal:
return k
for x in nums:
for v in [u + x, u - x, u ^ x]:
if v == goal:
return k + 1
if 0 <= v <= 1000 and v not in vis:
q.append((v, k + 1))
vis.add(v)
return -1
https://leetcode.com/problems/01-matrix/
class Solution:
def updateMatrix(self, mat: List[List[int]]) -> List[List[int]]:
m, n = len(mat), len(mat[0])
g = [[0] * n for _ in range(m)]
q = deque()
vis = set()
for i in range(m):
for j in range(n):
if mat[i][j] == 0:
vis.add((i, j))
q.append((i, j, 0))
while q:
i, j, k = q.popleft()
for ni, nj in [(i - 1, j), (i + 1, j), (i, j - 1), (i, j + 1)]:
if 0 <= ni < m and 0 <= nj < n and (ni, nj) not in vis:
vis.add((ni, nj))
q.append((ni, nj, k + 1))
g[ni][nj] = k + 1
return g
https://leetcode.com/problems/map-of-highest-peak/
class Solution:
def highestPeak(self, isWater: List[List[int]]) -> List[List[int]]:
m, n = len(isWater), len(isWater[0])
g = [[0] * n for _ in range(m)]
q = deque()
vis = set()
for i in range(m):
for j in range(n):
if isWater[i][j] == 1:
q.append((i, j, 0))
vis.add((i, j))
while q:
i, j, k = q.popleft()
for ni, nj in [(i - 1, j), (i + 1, j), (i, j - 1), (i, j + 1)]:
if 0 <= ni < m and 0 <= nj < n and (ni, nj) not in vis:
g[ni][nj] = k + 1
q.append((ni, nj, k + 1))
vis.add((ni, nj))
return g
https://leetcode.com/problems/walls-and-gates/
class Solution:
def wallsAndGates(self, rooms: List[List[int]]) -> None:
m, n = len(rooms), len(rooms[0])
q = deque()
vis = set()
for i in range(m):
for j in range(n):
if rooms[i][j] == 0:
vis.add((i, j))
q.append((i, j, 0))
elif rooms[i][j] == -1:
vis.add((i, j))
while q:
i, j, k = q.popleft()
for ni, nj in [(i - 1, j), (i + 1, j), (i, j - 1), (i, j + 1)]:
if 0 <= ni < m and 0 <= nj < n and (ni, nj) not in vis:
vis.add((ni, nj))
q.append((ni, nj, k + 1))
rooms[ni][nj] = k + 1
https://leetcode.com/problems/as-far-from-land-as-possible/
class Solution:
def maxDistance(self, grid: List[List[int]]) -> int:
m, n = len(grid), len(grid[0])
q = deque()
vis = set()
for i in range(m):
for j in range(n):
if grid[i][j] == 1:
q.append((i, j, 0))
vis.add((i, j))
ans = -1
while q:
i, j, k = q.popleft()
if grid[i][j] == 0:
ans = max(ans, k)
for ni, nj in [(i - 1, j), (i + 1, j), (i, j - 1), (i, j + 1)]:
if 0 <= ni < m and 0 <= nj < n and (ni, nj) not in vis:
q.append((ni, nj, k + 1))
vis.add((ni, nj))
return ans
https://leetcode.com/problems/minimum-genetic-mutation/
class Solution:
def minMutation(self, start: str, end: str, bank: List[str]) -> int:
q = deque()
q.append((start, 0))
vis = set()
vis.add(start)
bank = set(bank)
if end in vis:
return -1
while q:
s, k = q.popleft()
if s == end:
return k
s = list(s)
for i in range(8):
t = s[i]
for c in {'A', 'C', 'G', 'T'} - {t}:
s[i] = c
ns = ''.join(s)
if ns not in vis and ns in bank:
vis.add(ns)
q.append((ns, k + 1))
s[i] = t
return -1
https://leetcode.com/problems/all-nodes-distance-k-in-binary-tree/
class Solution:
def distanceK(self, root: TreeNode, target: TreeNode, k: int) -> List[int]:
def build(root, p):
par[root] = p
if root.left:
build(root.left, root)
if root.right:
build(root.right, root)
par = defaultdict(TreeNode)
build(root, None)
ans = []
q = deque()
q.append([target, 0])
vis = {target}
while q:
cur, step = q.popleft()
if step == k:
ans.append(cur.val)
continue
if cur.left and cur.left not in vis:
q.append([cur.left, step + 1])
vis.add(cur.left)
if cur.right and cur.right not in vis:
q.append([cur.right, step + 1])
vis.add(cur.right)
if par[cur] and par[cur] not in vis:
q.append([par[cur], step + 1])
vis.add(par[cur])
return ans
https://leetcode.com/problems/snakes-and-ladders/
class Solution:
def snakesAndLadders(self, board: List[List[int]]) -> int:
def pos(x):
r, c = (x - 1) // n, (x - 1) % n
if r % 2 == 1:
c = n - 1 - c
return (n - 1 - r, c)
n = len(board)
q = deque()
q.append([1, 0])
vis = {1}
if board[n - 1][0] == n * n:
return 1
while q:
x, k = q.popleft()
if x == n * n:
return k
for i in range(1, 7):
nx = x + i
ni, nj = pos(nx)
if nx <= n * n:
if board[ni][nj] != -1:
nx = board[ni][nj]
if nx not in vis:
vis.add(nx)
q.append([nx, k + 1])
return -1
https://leetcode.com/problems/web-crawler/
class Solution:
def crawl(self, startUrl: str, htmlParser: 'HtmlParser') -> List[str]:
p = startUrl.find('/', 7)
host = startUrl if p == -1 else startUrl[ : p]
a = [startUrl]
ans = {startUrl}
while a:
b = []
for s in a:
for url in htmlParser.getUrls(s):
if url not in ans and url.startswith(host):
ans.add(url)
b.append(url)
a = b
return list(ans)
https://leetcode.com/problems/water-and-jug-problem/
class Solution:
def canMeasureWater(self, x: int, y: int, t: int) -> bool:
q = deque()
q.append((x, y, 0))
vis = {(x, y)}
while q:
a, b, k = q.popleft()
if a + b == t:
return True
for na, nb in [(x, b), (a, y), (0, b), (a, 0), (min(x, a + b), max(0, a + b - x)), (max(0, a + b - y), min(y, a + b))]:
if (na, nb) not in vis:
q.append((na, nb, k + 1))
vis.add((na, nb))
return False
https://leetcode.com/problems/get-watched-videos-by-your-friends/
class Solution:
def watchedVideosByFriends(self, watchedVideos: List[List[str]], friends: List[List[int]], id: int, level: int) -> List[str]:
ans = Counter()
q = deque()
q.append((id, 0))
vis = {id}
while q:
u, k = q.popleft()
if k == level:
ans += Counter(watchedVideos[u])
continue
for v in friends[u]:
if v not in vis:
vis.add(v)
q.append((v, k + 1))
return [k for k, v in sorted(ans.items(), key = lambda x: (x[1], x[0]))]
https://leetcode.com/problems/shortest-path-with-alternating-colors/
class Solution:
def shortestAlternatingPaths(self, n: int, redEdges: List[List[int]], blueEdges: List[List[int]]) -> List[int]:
red, blue = defaultdict(list), defaultdict(list)
for u, v in redEdges:
red[u].append(v)
for u, v in blueEdges:
blue[u].append(v)
ans = [-1] * n
q = deque()
q.append((0, '', 0))
redVis, blueVis = {0}, {0}
while q:
u, c, k = q.popleft()
if ans[u] == -1 or ans[u] > k:
ans[u] = k
if c != 'r':
for v in red[u]:
if v not in redVis:
q.append((v, 'r', k + 1))
redVis.add(v)
if c != 'b':
for v in blue[u]:
if v not in blueVis:
q.append((v, 'b', k + 1))
blueVis.add(v)
return ans
https://leetcode.com/problems/open-the-lock/
class Solution:
def openLock(self, deadends: List[str], target: str) -> int:
vis = set(deadends)
if '0000' in vis:
return -1
q = deque()
q.append(('0000', 0))
vis.add('0000')
while q:
s, k = q.popleft()
if s == target:
return k
for d in [-1, 1]:
s = list(s)
for i in range(4):
t = s[i]
s[i] = str((int(s[i]) + d) % 10)
ns = ''.join(s)
if ns not in vis:
vis.add(ns)
q.append((ns, k + 1))
s[i] = t
return -1
https://leetcode.com/problems/stepping-numbers/
class Solution:
def countSteppingNumbers(self, low: int, high: int) -> List[int]:
ans = []
if low == 0:
ans.append(0)
q = deque()
for i in range(1, min(10, high + 1)):
q.append(i)
while q:
u = q.popleft()
if u > high:
break
if u >= low:
ans.append(u)
if u % 10 - 1 >= 0:
q.append(u * 10 + u % 10 - 1)
if u % 10 + 1 <= 9:
q.append(u * 10 + u % 10 + 1)
return ans
https://leetcode.com/problems/numbers-with-same-consecutive-differences/
class Solution:
def numsSameConsecDiff(self, n: int, k: int) -> List[int]:
ans = []
a = [_ for _ in range(1, 10)]
while a:
b = []
for x in a:
if len(str(x)) == n:
ans.append(x)
continue
if k == 0:
a.append(x * 10 + x % 10)
else:
if x % 10 - k >= 0:
a.append(x * 10 + x % 10 - k)
if x % 10 + k <= 9:
a.append(x * 10 + x % 10 + k)
a = b
return ans
https://leetcode.com/problems/minimum-jumps-to-reach-home/
class Solution:
def minimumJumps(self, forbidden: List[int], a: int, b: int, x: int) -> int:
q = deque()
q.append((0, 1, 0))
vis = {(0, 1)}
for v in forbidden:
vis.add((v, 0))
vis.add((v, 1))
while q:
p, back, k = q.popleft()
if p == x:
return k
if p + a <= 6005 and (p + a, 1) not in vis:
q.append((p + a, 1, k + 1))
vis.add((p + a, 1))
if back and p - b >= 0 and (p - b, 0) not in vis:
q.append((p - b, 0, k + 1))
vis.add((p - b, 0))
return -1