# 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…