Skip to content

Prepare For Coder Interview – Denny

  • Basic
  • Medium
  • Hard
  • Architect
  • Life

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

  • Review: DFS Problems
  • LintCode: Word Synthesis Problem
  • LintCode: Island City
  • LintCode: Fermat Point Of Graphs
  • Leetcode: Word Search II
  • Leetcode: Word Search
  • Leetcode: Web Crawler
  • Leetcode: Univalued Binary Tree
  • Leetcode: Tree Diameter
  • Leetcode: The Maze II
  • Leetcode: Ternary Expression Parser
  • Leetcode: Surrounded Regions
  • Leetcode: Sum of Distances in Tree
  • Leetcode: Smallest String Starting From Leaf
  • Leetcode: Smallest Rectangle Enclosing Black Pixels
  • Leetcode: Shortest Bridge
  • Leetcode: Remove Invalid Parentheses
  • Leetcode: Reconstruct Itinerary
  • Leetcode: Populating Next Right Pointers in Each Node
  • Leetcode: Path Sum
  • Leetcode: Pacific Atlantic Water Flow
  • Leetcode: Number of Islands
  • Leetcode: Number of Distinct Islands II
  • Leetcode: Number of Distinct Islands
  • Leetcode: Number of Closed Islands
  • Leetcode: Most Stones Removed with Same Row or Column
  • Leetcode: Minimum Knight Moves
  • Leetcode: Minesweeper
  • Leetcode: Maximum Level Sum of a Binary Tree
  • Leetcode: Maximum Depth of N-ary Tree
  • Leetcode: Maximum Average Subtree
  • Leetcode: Max Area of Island
  • Leetcode: Making A Large Island
  • Leetcode: Lowest Common Ancestor of Deepest Leaves
  • Leetcode: Letter Tile Possibilities
  • Leetcode: Keys and Rooms
  • Leetcode: Island Perimeter
  • Leetcode: Is Graph Bipartite?
  • Leetcode: House Robber III
  • Leetcode: Generalized Abbreviation
  • Leetcode: Flood Fill
  • Leetcode: Evaluate Division
  • Leetcode: Escape a Large Maze
  • Leetcode: Employee Importance
  • Leetcode: Cousins in Binary Tree
  • Leetcode: Course Schedule II
  • Leetcode: Course Schedule
  • Leetcode: Coloring A Border
  • Leetcode: Clone Graph
  • Leetcode: Binary Tree Right Side View
  • Leetcode: Android Unlock Patterns
  • Leetcode: All Paths From Source to Target
  • Leetcode: All Paths from Source Lead to Destination
  • Leetcode: 01 Matrix

See more blog_posts.

linkedin
github
slack

Post Views: 0
Posted in ReviewTagged #dfs, review

Post navigation

Leetcode: Letter Tile Possibilities
Leetcode: Market Analysis II

Leave a Reply Cancel reply

Your email address will not be published.

Tags

#array #backtracking #bfs #binarytree #bitmanipulation #classic #codetemplate #combination #dfs #dynamicprogramming #game #graph #greedy #heap #inspiring #interval #linkedlist #manydetails #math #misc #palindrome #recursive #slidingwindow #stack #string #subarray #trie #twopointer #twosum baseconversion binarysearch concurrency editdistance hashmap knapsack monotone oodesign presum redo review rotatelist series sql treetraversal unionfind

Recent Posts

  • Leetcode: Palindrome Partitioning III
  • Leetcode: Biggest Single Number
  • Leetcode: Max Consecutive Ones II
  • Leetcode: Minimum Cost to Connect Sticks
  • Leetcode: Minimum Swaps to Group All 1’s Together

Recent Comments

    Archives

    Categories

    • Amusing
    • Basic
    • Easy
    • Hard
    • Life
    • Medium
    • Resource
    • Review
    • Series
    • Uncategorized
    Proudly powered by WordPress | Theme: petals by Aurorum.