note0489.md

Leetcode 489. Robot Room Cleaner

• Type: Search (dfs)
• Approach:
  • Top-down dfs.
  • Use basic dfs backtrack thought but the question is a little bit tricky for recovering to its original state.
  • The original state includes its direction and cell postion.
  • Remember to backtrack whenever a move() takes because if robot.move() is True, it has to be move forward to another cell and it has to be recovered to the original state (cell, direction).
• Complexity:
  • Time: O(n)
  • Space: O(n)