What is the main strategy to solve Keys and Rooms?

The primary approach is graph traversal using DFS or BFS to visit all rooms starting from room 0 and collecting keys.

Can BFS be used instead of DFS for this problem?

Yes, BFS works equally well by processing rooms level by level using a queue while tracking visited rooms.

What if some rooms contain no keys?

Rooms with no keys are still counted as visited once entered. They must be marked visited to ensure correct traversal.

How do I avoid revisiting rooms unnecessarily?

Maintain a visited set or boolean array. Only add keys for unvisited rooms to the traversal structure.

What pattern does this problem exemplify?

Keys and Rooms exemplifies graph traversal with depth-first search pattern and the challenge of visiting all nodes in a connected graph with constraints.

#841

Medium

auto_awesome图·DFS·traversal

LeetCode 题解工作台

钥匙和房间

有 n 个房间，房间按从 0 到 n - 1 编号。最初，除 0 号房间外的其余所有房间都被锁住。你的目标是进入所有的房间。然而，你不能在没有获得钥匙的时候进入锁住的房间。当你进入一个房间，你可能会在里面找到一套不同的钥匙，每把钥匙上都有对应的房间号，即表示钥匙可以打开的房间。你可以拿上所有钥…

深度优先搜索广度优先搜索图

题目描述

有 n 个房间，房间按从 0 到 n - 1 编号。最初，除 0 号房间外的其余所有房间都被锁住。你的目标是进入所有的房间。然而，你不能在没有获得钥匙的时候进入锁住的房间。

当你进入一个房间，你可能会在里面找到一套 不同的钥匙，每把钥匙上都有对应的房间号，即表示钥匙可以打开的房间。你可以拿上所有钥匙去解锁其他房间。

给你一个数组 rooms 其中 rooms[i] 是你进入 i 号房间可以获得的钥匙集合。如果能进入所有房间返回 true，否则返回 false。

示例 1：

输入：rooms = [[1],[2],[3],[]]
输出：true
解释：
我们从 0 号房间开始，拿到钥匙 1。
之后我们去 1 号房间，拿到钥匙 2。
然后我们去 2 号房间，拿到钥匙 3。
最后我们去了 3 号房间。
由于我们能够进入每个房间，我们返回 true。

示例 2：

输入：rooms = [[1,3],[3,0,1],[2],[0]]
输出：false
解释：我们不能进入 2 号房间。

提示：

n == rooms.length
2 <= n <= 1000
0 <= rooms[i].length <= 1000
1 <= sum(rooms[i].length) <= 3000
0 <= rooms[i][j] < n
所有 rooms[i] 的值 互不相同

lightbulb

解题思路

方法一：DFS

我们可以使用深度优先搜索的方法遍历整张图，统计可以到达的节点个数，并利用数组 vis 标记当前节点是否访问过，以防止重复访问。

最后统计访问过的节点个数，若与节点总数相同则说明可以访问所有节点，否则说明存在无法到达的节点。

时间复杂度 $O(n + m)$ ，空间复杂度 $O(n)$ ，其中 $n$ 为节点个数，而 $m$ 为边的个数。

1

2

3

4

5

6

7

8

9

10

11

12

13

class Solution:
    def canVisitAllRooms(self, rooms: List[List[int]]) -> bool:
        def dfs(i: int):
            if i in vis:
                return
            vis.add(i)
            for j in rooms[i]:
                dfs(j)

        vis = set()
        dfs(0)
        return len(vis) == len(rooms)

speed

复杂度分析

指标	值
时间	O(N + E)
空间	O(N)

psychology

面试官常问的追问

外企场景

question_mark
Looks for a correct graph traversal mapping and edge handling.
question_mark
Checks if DFS and BFS alternatives are considered for visiting all rooms.
question_mark
Wants awareness of cycles and revisiting rooms when keys overlap.

warning

常见陷阱

外企场景

error
Forgetting to mark rooms as visited leading to infinite loops or redundant work.
error
Assuming keys must be used in numerical order instead of exploring available keys flexibly.
error
Not handling rooms with no keys correctly, which can block traversal if not checked.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Rooms may contain multiple keys for the same room, requiring careful visited tracking.
arrow_right_alt
Rooms can form disconnected components; determine accessibility from room 0 only.
arrow_right_alt
Keys could be nested or recursive, requiring iterative or recursive traversal strategies.

help

常见问题

外企场景

继续练习

#802 找到最终的安全状态 #797 所有可能的路径 #886 可能的二分法