841-KeysandRooms

Keys and Rooms

Problem can be found in here!

Solution: Depth-first Search

def canVisitAllRooms(rooms: List[List[int]]) -> bool:
    stack = [0]
    visited_rooms = set([0])
    while stack:
        room_num = stack.pop()
        for neighbor in rooms[room_num]:
            if neighbor not in visited_rooms:
                stack.append(neighbor)
                visited_rooms.add(neighbor)

    return len(visited_rooms) == len(rooms)

Explanation: Perform DFS to solve this problem and skip already visited rooms when encounters the same key to visited rooms.

Time Complexity: , Space Complexity: , where V and E is the number of rooms and number of keys, respectively.