LeetCode: Rooms and Keys

There are n rooms labeled from 0 to n-1, and each room may contain some keys to other rooms. Initially, you start in room 0, and your goal is to visit all the rooms. However, you can only enter a room if you have its key.

Solution Approach: DFS with Set

function canVisitAllRooms(rooms) {
  let visited = new Set()
  let keys = new Set()

  function dfs(currentRoom, currentKeys) {
    if (visited.has(currentRoom)) return
    visited.add(currentRoom)

    for (let key of rooms[currentRoom]) {
      keys.add(key)
    }

    for (let key of currentKeys) {
      dfs(key, keys)
    }
  }

  dfs(0, keys)
  return visited.size === rooms.length
}

Step-by-Step

Data Structures Used

• visited: A Set to keep track of rooms we've already visited
• keys: A Set to store all keys we've collected

DFS Implementation
The solution uses Depth-First Search (DFS) to traverse through the rooms. Here's how it works:

1. Start at room 0
2. Mark the current room as visited
3. Collect all keys in the current room
4. Use each available key to visit new rooms 5 Repeat the process for each accessible room

Key Steps in the Code

• Base Case: If we've already visited a room, return to avoid cycles
• Collecting Keys: Add all keys found in the current room to our key set
• Recursive Exploration: Try to visit each room we have a key for
• Final Check: Compare the number of visited rooms with total rooms

Example Walkthrough

Input: [[1], [2], [3], []]

Start at room 0, get key to room 1
Visit room 1, get key to room 2
Visit room 2, get key to room 3
Visit room 3 (empty room)
All rooms visited! Return true