DFS & BFS
June 3, 2021
BFSÂ solution
Introduction
Depth First Search and Breath First Search are extremely common graph traversal algorithms. The main difference is that in BFS visits nodes of the same level one at the same time, whereas DFS follows a node through the rabbit hole until the node no longer has any neighbors to visit. You'll typically perform DFS or BFS when the problem statement has a 2D matrix that requires non-obvious navigation, or a binary tree. There are also other deceptive inputs that initially seem like they require simple array processing or two-pointer processing but can only be answered via DFS/BFS. The example that follows will illustrate this.
An Example
Problem Statement
Given a string s that contains parentheses and letters, remove the minimum number of invalid parentheses to make the input string valid.
Return all the possible results. You may return the answer in any order.
BFS Algorithm
The key to this problem is to realize that we will need to remove a single open or close parentheses from every possible position and check to see if the newly formed string is a valid parentheses. If we go about removing 1 parentheses the first time from all possible positions, then another (which makes a total of two), then another on the third round, we can treat this like a BFS problem.
The code follows below:
BFS solution
The problem can also be solved via DFS. They key thing to remember is that we need to remove the minimum amount of characters until we encounter a valid parentheses. So we need to keep the track of the running minimum value so that our other depth first traversals don't go to deeper levels than the minimum we have encountered. The solution follows below:
DFS Solution
Practice Problems
MEDIUM
○ Letter Combinations of a Phone Number
○ Populating Next Right Pointers in Each Node II
○ Construct Binary Tree from Inorder and Postorder Traversal
HARD
○ Longest Increasing Path in a Matrix