Youwang Deng

I'm a software developer, familiar with C#, Java, JavaScript, focus on full stack development.

Leetcode BFS & DFS Note

15 Jul 2019 » Leetcode-BFS, Leetcode-DFS, Leetcode-Array, Leetcode-ArrayList, Leetcode-LinkedList, Algorithm
  • use queue to cache data
  • use queue.size() to mark level
  • use level to store result
  • use hashset to store visited elements
  • the entry point of loop or recursion is most important
  • return condition(prunning)
  • backtracking(brute force)
  • the problem could use DFS, consider using DP to reduce time complexity and space complexity
  • cache array & DFS = top-down approach
  • cache array & nested for loop = DP, bottom-up approach
  • N-Queens, diagnal(diag[row - j + N - 1] is true or false) and anti-diagnal check(antiDiag[row + j] is true or false), use 1D array to represent queen position

  • classic dfs program structure

      public static void dfs(List<List<String>> result, List<String> path, int index) {
      // 1. end condition, add path to result and return

      // 2. prunning, multiple return conditions

      // 3. for loop dfs condition, have to prunning and restore state after dfs
  }
  • how to reduce time complexity
    • cache result
    • prunning
  • avoid duplicate or infinite loop
    • use visited set or boolean array

Related Posts