Review: DFS Problems

Posted on August 12, 2019October 4, 2019 by braindenny

Here we try to compile a list of inspiring DFS problems.

CheatSheet: Leetcode For Code Interview

Basic Abstractions

Name	Summary
dfs avoid duplicate caculations	Maintain state array. And update it at the end of dfs Leetcode: Course Schedule

Scenarios
Code Skeleton
Questions

Name	Example
In matrix dfs, change cell to impossible value to avoid state hashmap	Leetcode: Word Search II

dfs get results from return value or input parameters

// https://code.dennyzhang.com/android-unlock-patterns
func dfs(pos int, visited []bool, count int, middles [][]int) int {
    // find one path
    if count == 0 {
        return 1
    }
    res := 0
    visited[pos] = true
    for i:=1; i<=9; i++ {
        if !visited[i] {
            // from pos -> to: adjacent or the middle node visited
            if middles[pos][i] == 0|| visited[middles[pos][i]] {
                res += dfs(i, visited, count-1, middles)
            }
        }
    }
    // backtracking
    visited[pos] = false
    return res
}

// https://code.dennyzhang.com/android-unlock-patterns
func dfs(pos int, visited []bool, count int, middles [][]int, res *int) {
    // find one path
    if count == 0 {
        *res += 1
    }
    visited[pos] = true
    for i:=1; i<=9; i++ {
        if !visited[i] {
            // from pos -> to: adjacent or the middle node visited
            if middles[pos][i] == 0|| visited[middles[pos][i]] {
                 dfs(i, visited, count-1, middles, res)
            }
        }
    }
    // backtracking
    visited[pos] = false
}

See all dfs problems: #dfs

See more blog_posts.

Post Views: 0