There are n rooms labeled from 0 to n - 1 and all the rooms are locked except for room 0. Your goal is to visit all the rooms. However, you cannot enter a locked room without having its key.
When you visit a room, you may find a set of distinct keys in it. Each key has a number on it, denoting which room it unlocks, and you can take all of them with you to unlock the other rooms.
Given an array rooms where rooms[i] is the set of keys that you can obtain if you visited room i, return true if you can visit all the rooms, or false otherwise.
Example 1:
Input: rooms = [[1],[2],[3],[]] Output: true Explanation: We visit room 0 and pick up key 1. We then visit room 1 and pick up key 2. We then visit room 2 and pick up key 3. We then visit room 3. Since we were able to visit every room, we return true.
Example 2:
Input: rooms = [[1,3],[3,0,1],[2],[0]] Output: false Explanation: We can not enter room number 2 since the only key that unlocks it is in that room.
Constraints:
n == rooms.length2 <= n <= 10000 <= rooms[i].length <= 10001 <= sum(rooms[i].length) <= 30000 <= rooms[i][j] < nrooms[i] are unique.
The description was taken from https://leetcode.com/problems/keys-and-rooms/.
#DFS
#O(N) Time, O(N) Space
class Solution:
def canVisitAllRooms(self, rooms: List[List[int]]) -> bool:
seen = {}
def dfs(room:int) -> None:
if room in seen:
return
seen[room] = True
for key in rooms[room]:
if key not in seen:
dfs(key)
dfs(0)
return len(seen) == len(rooms)#BFS
#O(N) Time, O(N) Space
class Solution:
def canVisitAllRooms(self, rooms: List[List[int]]) -> bool:
seen = {}
def bfs(room:int) -> None:
queue = collections.deque([(0)])
while queue:
room = queue.popleft()
seen[room] = True
for key in rooms[room]:
if key not in seen:
queue.append((key))
bfs(0)
return len(seen) == len(rooms)To solve this problem, we can visit the first room, grab its set of keys and visit the corresponding rooms.
We will then continue that process on each room we have keys for until we have not received any more keys.
At that point, we will see if the number of rooms that we had seen is equal to the number of rooms that were given.
Let's start by initializing the dictionary for seen rooms.
seen = {}
Next, we will build our recursive, DFS function that will be run on a given room.
def dfs(room:int) -> None:
If the room has already been seen, then we will return because we already have the keys for it.
if room in seen:
return
Otherwise, we will mark the room as seen, grab each key that we have in the room, and if we have not yet seen a room for each corresponding key, we will visit the room next.
seen[room] = True
for key in rooms[room]:
if key not in seen:
dfs(key)
Now that we have our DFS function built, we will begin visiting the first room's set of rooms.
dfs(0)
After our DFS has been completed, we will return whether we visited all of the rooms by comparing the number of rooms we had seen.
return len(seen) == len(rooms)
For the BFS version, the only difference is we'll just need to swap out a queue for our recursive call stack.
def bfs(room:int) -> None:
queue = collections.deque([(0)])
while queue:
room = queue.popleft()
seen[room] = True
for key in rooms[room]:
if key not in seen:
queue.append((key))