DFS & BFS - cocoder39/coco39_LC GitHub Wiki

dfs vs bfs

It depends on the **structure of the search tree** and **the number and location of solutions** (aka searched-for items). If you know a solution is not far from the root of the tree, a breadth first search (BFS) might be better. If the tree is very deep and solutions are rare, depth first search (DFS) might take an extremely long time, but BFS could be faster. If the tree is very wide, a BFS might need too much memory, so it might be completely impractical. If solutions are frequent but located deep in the tree, BFS could be impractical. If the search tree is very deep you will need to restrict the search depth for depth first search (DFS), anyway (for example with iterative deepening).

bfs

shortest path (BFS Shortest Path Template)

• 127. Word Ladder
• 126. Word Ladder II
• 1197. Minimum Knight Moves
• 864. Shortest Path to Get All Keys
• 317. Shortest Distance from All Buildings
• 675. Cut Off Trees for Golf Event
• 847. Shortest Path Visiting All Nodes
• 815. Bus Routes
• 286. Walls and Gates
• 854. K Similar Strings
• 1091. Shortest Path in Binary Matrix

dfs

• 419. Battleships in a Board
• 79. Word Search (follow up is trie)
• 211. Add and Search Word Data structure design (dfs, 208. Implement Trie (Prefix Tree))
• 294. Flip Game II (backtracking)
• 131. Palindrome Partitioning (dp, dfs)
• 489. Robot Room Cleaner
• 827. Making A Large Island (uf is also an option)
• 490. The Maze
• 733. Flood Fill

Distribute elements to K buckets (dfs + pruning)

• 1723. Find Minimum Time to Finish All Jobs
• 698. Partition to K Equal Sum Subsets(416. Partition Equal Subset Sum)
• 473. Matchsticks to Square

tree (divide-and-conquer)

• 104. Maximum Depth of Binary Tree (dfs or bfs)
• 111. Minimum Depth of Binary Tree (dfs or bfs)
• 110. Balanced Binary Tree (top-down dfs or bottom-up dfs)
• 100. Same Tree (recursion + dfs or iteration + stack)
• 1443. Minimum Time to Collect All Apples in a Tree

matrix

• 200. Number of Islands (305. Number of Islands II)
• 1905. Count Sub Islands
• similar problems:
  • number-of-islands-ii
  • number-of-connected-components-in-an-undirected-graph
  • number-of-distinct-islands
  • 695. Max Area of Island
• 694. Number of Distinct Islands
• 529. Minesweeper

combination

• 17. Letter Combinations of a Phone Number
• 22. Generate Parentheses
• 254. Factor Combinations (avoid duplication)
• 77. Combinations
• 39. Combination Sum (avoid duplication)
• 40. Combination Sum II (avoid duplication)
• 216. Combination Sum III
• 377. Combination Sum IV (dp / dfs)
• 1643. Kth Smallest Instructions (combination sequence)

permutation

• 31. Next Permutation
• 46. Permutations
• 47. Permutations II
• 267. Palindrome Permutation II (266. Palindrome Permutation + 47. Permutations II)
• 60. Permutation Sequence

set

• 78. Subsets
• 90. Subsets II (dedupe)
• 698. Partition to K Equal Sum Subsets

bitmask

• 51. N-Queens
• 52. N Queens II

recursion

• 341. Flatten Nested List Iterator

backtrack

• 37. Sudoku Solver (36. Valid Sudoku)
• 301. Remove Invalid Parentheses (backtrack with optimization)
• 140. Word Break II (backtrack with optimization, can also be solved with dp)