Leetcode patterns- DFS

After 1000 medium level problems. write down the patterns what i have learned .

I have been started on leetcode since end of 2020 . Until Jan 2022 I have done enough problems and should have a break to write down what i have learned, now i am at 1004th problem .

There are a few patterns be identified when solving the problems, I want to share all these patterns also with some high ranking medium leetcode problems to you , beside the problems itself, more important is to master the nice algorithm ideas used in real projects.

Why medium level ? they are more likely matched with the difficulty level of either interview problems or real projects problems . in short, if you are not beginner (or you are, but after trying 10–20 easy ones you will want to medium) or ACM competition, medium level is best .

This is the 1st one — Depth First Search

Core idea

def dfs(input, visited): 
     if stop_condition or visited:
          return information to parent
     next_inputs = get_next_inputs()
     for next_input in next_inputs:
         visited |= current
         res = dfs(next_input, visited)
         # visited -= {current}  depends, some issue need to restore the search state
      return information needed by parent

so the idea is very simple. pass in whatever needed , check stop_condition (this should be the first thing for every recursive function), save into visited if needed and get next states (input) for next DFS (restore visited state (or search path) if needed ) repeat the same until reach the stop_condition; return the information needed by caller .

With on this base pattern , there are few sub patterns : matrix , tree, 1-N mapping (array or hashtable) relationship .

DFS with matrix

def dfs(r, c, row, col, visited):
    if r < 0 or c < 0 or r == row or c == col or (r,c) in visited or grid[r][c] == bad_value :
        return False
    visited |= {node}
    res = dfs(r-1, c, row, col, visited) or dfs (r+1, c, row, col, visited) \
          dfs(r, c-1, row, col, visited) or dfs (r, c+1, row, col, visited)
    visited -= {(r,c)} # incase need to restore state
    return res

The searching scope is matrix, so there be 4 directions to used for “next_inputs” : left, right, top down; stop_condition will be when reach the border or matrix[row][col] matched with some…