LC-0841 Medium LeetCode

841. Keys and Rooms

Depth-First Search Breadth-First Search Graph

Read the full problem statement on LeetCode.

Difficulty: medium Acceptance: 75% Topics: Depth-First Search, Breadth-First Search, Graph

Reading material

Reference solution (spoiler · python)

# Time:  O(n!)
# Space: O(n)

class Solution(object):
    def canVisitAllRooms(self, rooms):
        """
        :type rooms: List[List[int]]
        :rtype: bool
        """
        lookup = set([0])
        stack = [0]
        while stack:
            node = stack.pop()
            for nei in rooms[node]:
                if nei not in lookup:
                    lookup.add(nei)
                    if len(lookup) == len(rooms):
                        return True
                    stack.append(nei)
        return len(lookup) == len(rooms)

Solution from kamyu104/LeetCode-Solutions · MIT