Go back

LeetCode Hot 100——图论篇（DFS、BFS、拓扑排序、Trie）

LeetCode Hot 100 · 图论篇

图论是面试手撕的高频大类，但 Hot 100 里的图论题其实没有「最小生成树」「最短路」这种重量级算法，反而是四道「套路模板题」，只要掌握四个模板就能通杀一大片：

这四题的共同点是：模板极其固定，面试官看的就是你能不能把「为什么这么写」讲清楚，以及边界条件有没有踩坑。下面逐题拆解，每一题都按「题意 → 难点易错点 → 暴力解法 → 最优解法 → 多解法对比 → CodeTop 变体」的顺序展开，直接照着手撕。

#200 岛屿数量

题意

给你一个 m x n 的二进制矩阵 grid，'1' 表示陆地，'0' 表示水，返回岛屿数量——岛屿是被水环绕的四连通陆地连通块。

输入：grid = [["1","1","0"],["1","1","0"],["0","0","1"]]
输出：2   // 左上角一块大陆 + 右下角一个孤岛

题目本质：DFS/BFS 连通块计数。遍历矩阵，每遇到一个未访问的 '1' 就是一座新岛屿，然后用 DFS 把整块连通陆地「染色」（改成 '0'），避免重复统计。

现实类比：卫星地图统计陆地板块——扫描地图的每个格子，发现一块新陆地就把整块大陆「沉」成海水（标记已访问），最后统计「发现新陆地」的次数就是岛屿数。

难点与易错点

  1. '1' 是字符不是数字 1。grid 是 char[][]，判断时必须写 grid[r][c] == '1'，写 == 1 会直接编译报错或逻辑错误。这是新手最常见的低级失误。
  2. 原地沉岛 vs visited 数组：用「把 '1' 改成 '0'」来标记已访问最省空间，但面试官常追问「如果要求不能修改原矩阵怎么办」——那就退回 boolean[][] visited 数组。
  3. 空矩阵边界：grid.length == 0 或 grid[0].length == 0 时，直接访问 grid[0] 会越界。虽然 LeetCode 官方用例一般非空，但工业级写法必须先判空。
  4. 递归栈溢出：如果整张图全是陆地（一个 1000 × 1000 的大岛），DFS 递归深度可达 10^6 级，直接 StackOverflowError。这是 DFS 方案的隐藏坑，此时要换成 BFS 或并查集。
  5. 四连通 vs 八连通：本题只算上下左右四个方向，斜对角不算相连。写成八方向会多算/漏算岛屿。

解法一：暴力 / 直观（BFS + visited 数组）

最直观的写法：对每个 '1' 触发一次 BFS，把和它连通的所有陆地用一个 visited 数组标记掉。思路清晰、不会栈溢出，但多了一份 visited 数组的空间开销。

class Solution {
    public int numIslands(char[][] grid) {
        if (grid == null || grid.length == 0) return 0;
        int rows = grid.length, cols = grid[0].length;
        boolean[][] visited = new boolean[rows][cols];
        int count = 0;

        int[][] dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

        for (int r = 0; r < rows; r++) {
            for (int c = 0; c < cols; c++) {
                // 发现新岛屿：陆地且未访问
                if (grid[r][c] == '1' && !visited[r][c]) {
                    count++;
                    Deque<int[]> queue = new ArrayDeque<>();
                    queue.offer(new int[]{r, c});
                    visited[r][c] = true;

                    while (!queue.isEmpty()) {
                        int[] cur = queue.poll();
                        for (int[] d : dirs) {
                            int nr = cur[0] + d[0], nc = cur[1] + d[1];
                            if (nr >= 0 && nr < rows && nc >= 0 && nc < cols
                                    && grid[nr][nc] == '1' && !visited[nr][nc]) {
                                visited[nr][nc] = true;
                                queue.offer(new int[]{nr, nc});
                            }
                        }
                    }
                }
            }
        }
        return count;
    }
}

复杂度推导：

空间复杂度：visited 数组 O(mn)，BFS 队列最坏情况（一整层全是陆地，如锯齿状）可达 O(mn)，总 O(mn)。

瓶颈在哪：思路正确、时间复杂度已最优，但额外申请了一份 visited 数组，空间上是「双份」（visited + 队列），代码也偏长。解法二用「原地沉岛」把这部分空间省掉。

解法二：优化 / 最优（DFS 沉岛）

核心优化：不再单独维护 visited，而是把访问过的陆地直接改成 '0'（沉岛），用原矩阵自己充当「已访问」标记，省掉一整份 O(mn) 的 visited 数组，代码也更短。

class Solution {
    private int rows, cols;
    private char[][] grid;

    public int numIslands(char[][] grid) {
        if (grid == null || grid.length == 0) return 0;
        this.grid = grid;
        rows = grid.length;
        cols = grid[0].length;
        int count = 0;

        for (int r = 0; r < rows; r++) {
            for (int c = 0; c < cols; c++) {
                if (grid[r][c] == '1') { // 发现新岛屿
                    count++;
                    dfs(r, c); // 把整块岛屿沉掉（标记已访问）
                }
            }
        }
        return count;
    }

    private void dfs(int r, int c) {
        // 越界或已访问（水域）则返回
        if (r < 0 || r >= rows || c < 0 || c >= cols || grid[r][c] != '1') return;

        grid[r][c] = '0'; // 沉岛：标记为已访问

        // 向四个方向扩展
        dfs(r - 1, c);
        dfs(r + 1, c);
        dfs(r, c - 1);
        dfs(r, c + 1);
    }
}

复杂度逐步推导：

空间复杂度：原地修改，没有 visited 数组。唯一额外空间是 DFS 递归调用栈——最坏情况下（整张图连成一条蛇形或一整块陆地）递归深度可达到 O(mn)，因此 最坏 O(mn)。若对栈溢出敏感，把 dfs 换成 BFS（队列实现）即可把「深度」问题换成「队列内存」问题。

💭 思考：为什么「沉岛」能替代 visited 数组？——visited 数组的职责是「标记这个格子已经处理过，别再数一遍」，而原矩阵里 '1' 一旦改成 '0'，外层循环和 DFS 都不会再碰它，就天然完成了标记。把「已访问」编码进数据本身，省掉一整份 O(mn) 的额外空间，代码也更短。看到「遍历矩阵统计连通块」这个信号，先想到「遇到一个未访问的 1 就计数 + 把整块染色」，再问一句「能不能原地标记」——能的话就是沉岛法；若题目要求不改原矩阵，退回 visited 数组。

多解法对比

解法时间复杂度空间复杂度适用场景
BFS + visited 数组O(mn)O(mn)（visited + 队列）不允许改原矩阵、怕栈溢出
DFS 沉岛（最优）O(mn)O(mn)（仅递归栈，无 visited）默认手撕写法，代码最短
并查集 Union-FindO(mn · α(mn))O(mn)需要动态合并/统计连通块大小

为什么选 DFS 沉岛为最优：这题约束下（m, n 通常不大、允许改原矩阵），DFS 沉岛时间达到下界 O(mn)（每个格子至少要看一眼），空间省掉 visited 数组，代码最短最好背。BFS 版本只是「防栈溢出」的备胎；并查集虽然思路通用，但常数大、代码长，除非题目追问「动态加陆地」否则不必用。

CodeTop 变体

#994 腐烂的橘子

题意

m x n 矩阵：0 空格、1 新鲜橘子、2 腐烂橘子。每分钟，每个腐烂橘子会把它四连通方向的新鲜橘子也变腐烂。返回直到没有新鲜橘子为止所需的最少分钟数；若不可能全腐烂，返回 -1。

输入：grid = [[2,1,1],[1,1,0],[0,1,1]]
输出：4

题目本质：多源 BFS。所有腐烂橘子同时向外扩散，BFS 天然支持多起点同时扩散，扩散的「层数」就是经过的分钟数。

现实类比：病毒传播计时——多个感染源同时向四周蔓延，BFS 按轮次（每轮 = 1 分钟）扩散，记录轮数（层数）就是最短传播时间。

难点与易错点

  1. 必须「多源同时入队」而不是逐个单源 BFS 取 max：如果对每个腐烂橘子单独做一次 BFS 再取最大值，虽然数值上能碰对，但会大量重复访问，复杂度退化；正确做法是初始把所有腐烂橘子一次性入队，一起扩散。
  2. 按层扩散的写法：每「分钟」必须一次性处理完当前队列里的一整层（用 levelSize = deque.size() 固定本层大小），不能边出队边把新腐烂的橘子混进同一分钟。这是 BFS 求「最短层数」的标准坑。
  3. minutes 只在真正有新鲜橘子可腐烂时才 +1：如果某轮队列还有腐烂橘子、但周围已没有新鲜橘子了，这轮不应计时间（判断条件里加 fresh > 0）。
  4. 最后用 fresh 计数判断 -1：不要 BFS 结束后再遍历一遍数 1（虽然也对），维护一个 fresh 变量，每腐烂一个就 --，最后 fresh > 0 就返回 -1，干净且省一次全扫描。
  5. 新鲜橘子被多源同时盯上：同一新鲜橘子可能同时和多个腐烂源相邻，只有第一个把它染成 2 的源能入队，之后要立刻改 grid[nr][nc] = 2 防止重复入队（等价于 visited 标记）。

解法一：暴力 / 直观（逐分钟全矩阵模拟）

最贴近「每分钟」语义的写法：每过一分钟，扫描整个矩阵，把所有「新鲜且四邻有腐烂」的橘子标记出来，一次性染成腐烂，重复直到某分钟不再有新腐烂；若还有新鲜橘子则返回 -1。

class Solution {
    public int orangesRotting(int[][] grid) {
        int rows = grid.length, cols = grid[0].length;
        int[][] dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
        int minutes = 0;

        while (true) {
            // 本轮要被腐烂的新鲜橘子（先收集，后统一染色，避免本轮内连环传播）
            List<int[]> toRot = new ArrayList<>();
            for (int r = 0; r < rows; r++) {
                for (int c = 0; c < cols; c++) {
                    if (grid[r][c] != 1) continue; // 只看新鲜橘子
                    for (int[] d : dirs) {
                        int nr = r + d[0], nc = c + d[1];
                        if (nr >= 0 && nr < rows && nc >= 0 && nc < cols
                                && grid[nr][nc] == 2) {
                            toRot.add(new int[]{r, c});
                            break;
                        }
                    }
                }
            }

            if (toRot.isEmpty()) break; // 本轮无新腐烂，扩散停止

            for (int[] cell : toRot) grid[cell[0]][cell[1]] = 2; // 统一染腐烂
            minutes++;
        }

        // 检查是否还有新鲜橘子
        for (int r = 0; r < rows; r++)
            for (int c = 0; c < cols; c++)
                if (grid[r][c] == 1) return -1;

        return minutes;
    }
}

复杂度推导：

空间复杂度：toRot 列表最坏装 O(mn) 个橘子，O(mn)（若用临时标记值 3 代替列表可降到 O(1)）。

瓶颈在哪：每一分钟都全量重扫整个矩阵，做了大量「上轮已经确定不会腐烂」的无效比较，时间退化到平方级。BFS 的核心价值就是只从「刚腐烂的橘子」往外推，而不是每轮全盘重扫。

解法二：优化 / 最优（多源 BFS）

把所有腐烂橘子初始一次性入队，之后每层扩散一轮 = 1 分钟，直到队列空或没有新鲜橘子。每个橘子只被处理一次，时间压到 O(mn)。

class Solution {
    public int orangesRotting(int[][] grid) {
        int rows = grid.length, cols = grid[0].length;
        Deque<int[]> deque = new ArrayDeque<>();
        int fresh = 0; // 新鲜橘子总数

        // 初始化：统计新鲜橘子，所有腐烂橘子同时入队（多源）
        for (int r = 0; r < rows; r++) {
            for (int c = 0; c < cols; c++) {
                if (grid[r][c] == 2) deque.offer(new int[]{r, c});
                else if (grid[r][c] == 1) fresh++;
            }
        }

        int[][] dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
        int minutes = 0;

        // BFS 按层（分钟）扩散；没有新鲜橘子就无需继续
        while (!deque.isEmpty() && fresh > 0) {
            minutes++;
            int levelSize = deque.size(); // 固定本层大小，保证「每分钟」扩散一轮

            while (levelSize-- > 0) {
                int[] cur = deque.poll();

                for (int[] d : dirs) {
                    int nr = cur[0] + d[0], nc = cur[1] + d[1];
                    if (nr >= 0 && nr < rows && nc >= 0 && nc < cols
                            && grid[nr][nc] == 1) {
                        grid[nr][nc] = 2; // 新鲜橘子腐烂
                        fresh--;
                        deque.offer(new int[]{nr, nc});
                    }
                }
            }
        }

        return fresh > 0 ? -1 : minutes; // 仍有新鲜橘子则不可能全腐烂
    }
}

复杂度逐步推导：

空间复杂度：队列最坏情况下装下所有 m × n 个橘子（例如棋盘格交错时几乎全入队），O(mn)。

💭 思考：为什么腐烂橘子必须「所有源同时入队」，而不是逐个单源 BFS 取 max？——先看暴力模拟为什么慢：每一分钟都全量重扫矩阵，把「上轮已确定不会腐烂」的格子又扫一遍，退化成 O(mn × T)。BFS 的关键改进是「只从刚腐烂的橘子往外推」。而「多源同时入队」保证了所有腐烂橘子在同一分钟一起扩散，层数才恰好等于分钟数；若逐个单源 BFS 再取 max，既无法表达「同时」的语义，又会大量重复访问同一格子。看到「多个起点同时扩散 + 求最短时间/距离」这个信号，就锁定「多源 BFS + 按层 levelSize 扩散」。

多解法对比

解法时间复杂度空间复杂度适用场景
逐分钟全矩阵模拟O(mn × T)，最坏 O((mn)²)O(mn)只想快速写出直观思路，不追求最优
多源 BFS（最优）O(mn)O(mn)标准手撕答案，天然支持多源同时扩散

为什么选多源 BFS 为最优：这题约束下 m, n ≤ 10 时两个解法都能过，但 m, n 一大（如 100 × 100 且橘子排成长链，T ≈ 10^4），模拟法直接 10^8 级起步、容易 TLE。多源 BFS 每个格子只碰一次，时间线性，且「层数 = 分钟数」的语义天然契合题意，面试官要的就是这个。

CodeTop 变体

#207 课程表

题意

numCourses 门课编号 [0, numCourses-1]，prerequisites[i] = [a, b] 表示要先学 b 才能学 a。判断能否完成所有课程——等价于判断这张有向图是否无环。

输入：numCourses = 2, prerequisites = [[1,0]]
输出：true   // 先学 0 再学 1，可完成
输入：numCourses = 2, prerequisites = [[1,0],[0,1]]
输出：false  // 0 和 1 互相依赖，成环，永远学不完

题目本质：拓扑排序（Kahn 算法）。BFS 从入度为 0 的节点开始，逐步「删边」，若最终处理掉的节点数等于 numCourses，则无环、可完成。

现实类比：工厂装配线——没有前置依赖的工序先做（入度 0），做完一道就把依赖它的后续工序的依赖数减 1，依赖全清空的工序再排队；若所有工序都能排上，则流水线无死锁。

难点与易错点

  1. 边的方向：[a, b] 表示「先修 b 才能修 a」，所以图中是 b → a（b 指向 a），建邻接表要写 adj.get(b).add(a) 并让 inDegree[a]++。方向写反会得到完全相反的结果。
  2. 自环与重复边：[a, a] 是自环，inDegree[a] 会 +1 且永远无法被清零（因为只有 a 的入度被减时才可能清，但 a 出队前自己入度不为 0）→ 会被正确判 false，但要心里清楚为什么。重复边 [a,b] 出现两次会让 inDegree[a] 多加，虽然本题不影响最终「是否成环」的结论，但建图时最好去重或用 Set 存边。
  3. 入度为 0 的节点要先全部入队：Kahn 的起点是所有入度为 0 的节点，不是只入队一个，否则会漏掉「多个独立起点」的情况。
  4. 用 count 统计处理数，而不是遍历后判：BFS 结束时若 count < numCourses，说明剩下的是成环的一圈（它们的入度永远 ≥ 1，进不了队列），此时判 false。这是判环的关键。
  5. DFS 判环要用「三色标记」：如果换 DFS 写法，不能只用一个 visited，必须区分「本轮路径上（访问中）」和「历史已处理」，否则会把「后访问到的已处理节点」误判成环。

解法一：暴力 / 直观（逐起点 DFS 找环）

最朴素的想法：对每个课程，从它出发 DFS，看能不能走回到它自己（即它是否落在某个环上），只要有一个课程在环上就返回 false。缺点是每个节点都从头 DFS 一遍，大量重复遍历。

class Solution {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        List<List<Integer>> adj = new ArrayList<>();
        for (int i = 0; i < numCourses; i++) adj.add(new ArrayList<>());
        for (int[] p : prerequisites) adj.get(p[1]).add(p[0]); // b → a

        // 对每个课程为起点，检查它是否在某个环上
        for (int i = 0; i < numCourses; i++) {
            boolean[] onPath = new boolean[numCourses];
            if (dfs(i, adj, onPath)) return false; // 发现环
        }
        return true;
    }

    // 从 cur 出发，若能走回到「当前路径上的节点」，说明有环
    private boolean dfs(int cur, List<List<Integer>> adj, boolean[] onPath) {
        if (onPath[cur]) return true; // 回到路径上的节点 → 成环
        onPath[cur] = true;
        for (int next : adj.get(cur)) {
            if (dfs(next, adj, onPath)) return true;
        }
        onPath[cur] = false; // 回溯，撤销本路径标记
        return false;
    }
}

复杂度推导：

空间复杂度：递归调用栈最深 O(V)，onPath 数组每次 O(V)，O(V)。

瓶颈在哪：每个起点都重新遍历整张图，重复计算严重，图一密（E 接近 V²）就是 O(V³) 级别，必超时。优化方向是「每个节点只处理一次」——这正是拓扑排序/三色 DFS 的思路。

解法二：优化 / 最优（Kahn 拓扑排序）

用「入度」驱动 BFS：入度为 0 的课程没有前置依赖、可以直接修，修完后把它后继课程的入度减 1，减到 0 又可以修。每个节点、每条边只被处理一次，线性时间判环。

class Solution {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        int[] inDegree = new int[numCourses];
        // 邻接表：先统一初始化，避免 computeIfAbsent 的额外开销，代码也更直白
        List<List<Integer>> adj = new ArrayList<>();
        for (int i = 0; i < numCourses; i++) adj.add(new ArrayList<>());

        // 建图：b → a（先修 b 才能修 a）
        for (int[] pre : prerequisites) {
            int a = pre[0], b = pre[1];
            adj.get(b).add(a);
            inDegree[a]++;
        }

        // Kahn 算法：所有入度为 0 的课程先入队
        Deque<Integer> deque = new ArrayDeque<>();
        for (int i = 0; i < numCourses; i++) {
            if (inDegree[i] == 0) deque.offer(i);
        }

        int count = 0; // 已完成的课程数
        while (!deque.isEmpty()) {
            int course = deque.poll();
            count++;

            // 修完该课程，其后继课程入度减 1
            for (int next : adj.get(course)) {
                if (--inDegree[next] == 0) {
                    deque.offer(next); // 入度清零，可以修了
                }
            }
        }

        return count == numCourses; // 所有课程都处理过则无环
    }
}

复杂度逐步推导：

空间复杂度：邻接表存 E 条边 O(V + E)，inDegree 数组 O(V)，队列最坏 O(V)，总 O(V + E)。

💭 思考：课程表为什么从「逐起点 DFS 找环」改成「入度驱动的拓扑排序」？——先看暴力版病在哪：对每个课程都从头 DFS 一遍看能不能走回自己，每个节点被重复遍历，图一密就是 O(V³)。关键观察：判断能否完成 = 判断有向图是否无环，而「无环」等价于「存在一个拓扑序」，也就是「总能找到入度为 0 的节点先做」。于是换成入度驱动：入度 0 的课程先入队，修完后把后继课程入度减 1，减到 0 又可以修，每个节点每条边只处理一次。看到「依赖关系 + 判断能否全部完成 / 求一个顺序」这个信号，就想到拓扑排序（Kahn），而不是去逐个找环。

多解法对比

解法时间复杂度空间复杂度适用场景
逐起点 DFS 找环O(V × (V + E))O(V)图极小、只求过、不追性能
三色 DFS 判环O(V + E)O(V)（递归栈）想要 DFS 版最优解，或需顺带记录访问顺序
Kahn 拓扑排序（最优）O(V + E)O(V + E)标准手撕答案，天然输出拓扑序

为什么选 Kahn 为最优：这题约束下（numCourses 可达 10^5 级），逐起点 DFS 的 O(V²) 直接爆掉；Kahn 与三色 DFS 都是 O(V + E) 的线性最优，但 Kahn 用「入度 + 队列」实现，不会递归栈溢出、代码更稳，且稍加改动（记录 count 顺序）就能直接升级成 210 课程表 II 输出拓扑序，复用性最强。

CodeTop 变体

#208 实现 Trie（前缀树）

题意

实现 Trie 类，包含三个方法：insert(word) 插入字符串；search(word) 返回 word 是否作为完整单词存在于 Trie 中；startsWith(prefix) 返回是否存在以 prefix 开头的字符串。

Trie trie = new Trie();
trie.insert("apple");
trie.search("apple");   // true
trie.search("app");     // false（app 只是前缀，不是完整单词）
trie.startsWith("app"); // true

题目本质：26 叉树。每个节点有 26 个子指针（对应 a-z）和一个 end 标记；插入是「沿路径建节点、最后打标记」，查找是「沿路径走节点、看标记」。

现实类比：字典索引系统——每层按字母分成 26 个抽屉，单词的字母一层层定位抽屉，走到最后一个字母所在抽屉时打上「完整单词」标记；查前缀就是看能不能走到底，查单词还得看有没有「完整单词」标记。

难点与易错点

  1. search 和 startsWith 的区别只在「end 标记」：search("app") 必须走到 p 节点且 end == true；startsWith("app") 只要能走到 p 节点（路径不断）就返回 true。很多人忘记区分，导致 search 把「前缀」也当成单词。
  2. 字符转索引：int idx = c - 'a'，注意 c 是 char，直接减 'a' 得到 0~25。写成 c - 97 也行但可读性差；写错 c - '0' 会越界。
  3. 根节点是空节点：root 不存任何字符，它只是「起点的 26 个分叉」，插入时从 root 的子节点开始建。不要把第一个字符塞进 root 本身。
  4. end 标记在单词最后一个字符的节点上：insert("apple") 后，end = true 打在 e 节点，而不是 root 或 a 节点。
  5. 空间爆炸风险：每个节点固定 26 个引用，若单词量极大且无公共前缀，节点数 = 总字符数，空间是 26 × 总字符数 级别。面试常追问「26 太大怎么优化」→ 用 HashMap<Character, Node> 按需存子节点（省空指针，但常数更大）。

解法一：暴力 / 直观（HashSet 存全部单词）

最省事的写法：用 HashSet 存所有单词，insert 直接 add，search 直接 contains，startsWith 遍历所有单词逐个判断 startsWith。

class Trie {
    private final Set<String> set = new HashSet<>();

    public void insert(String word) {
        set.add(word);
    }

    public boolean search(String word) {
        return set.contains(word);
    }

    public boolean startsWith(String prefix) {
        for (String w : set) {
            if (w.startsWith(prefix)) return true; // 遍历所有单词判断前缀
        }
        return false;
    }
}

复杂度推导：

空间复杂度：存下所有单词总字符数，O(N × L)，N 为单词数、L 为平均长度。

瓶颈在哪：search 已是 O(1) 级别，但 startsWith 每次都要遍历所有单词做前缀匹配。一旦「前缀查询」频繁（这是 Trie 最核心的使用场景，如搜索引擎联想、路由匹配），O(N × L) 完全扛不住。Trie 的价值就是把「前缀查询」也压到 O(L)。

解法二：优化 / 最优（26 叉树 Trie）

每个节点存 26 个子引用 + 一个 end 标记。用一个私有 find(s) 复用 search 和 startsWith 的查找逻辑：返回 0（路径中断不存在）/ 1（是前缀但不是完整单词）/ 2（是完整单词）。

class Trie {
    // 内部节点：26 个子节点 + 是否为完整单词结尾
    private static class Node {
        Node[] son = new Node[26];
        boolean end = false;
    }

    private final Node root = new Node();

    // 插入单词：沿字母逐层建节点，最后打 end 标记
    public void insert(String word) {
        Node cur = root;
        for (char c : word.toCharArray()) {
            int idx = c - 'a';
            if (cur.son[idx] == null) {
                cur.son[idx] = new Node(); // 按需创建节点
            }
            cur = cur.son[idx];
        }
        cur.end = true; // 最后一个字母节点标记为完整单词结尾
    }

    /**
     * 查找 s 在 Trie 中的状态：
     *  0 → 不存在（路径中断）
     *  1 → 是某单词的前缀但不是完整单词
     *  2 → 是完整单词
     */
    private int find(String s) {
        Node cur = root;
        for (char c : s.toCharArray()) {
            int idx = c - 'a';
            if (cur.son[idx] == null) return 0; // 路径中断，不存在
            cur = cur.son[idx];
        }
        return cur.end ? 2 : 1; // 2 = 完整单词，1 = 仅前缀
    }

    public boolean search(String word)       { return find(word) == 2; }
    public boolean startsWith(String prefix) { return find(prefix) != 0; }
}

复杂度逐步推导：

💭 思考：为什么 HashSet 能 O(1) 查单词，却扛不住前缀查询，必须上 Trie？——先看 HashSet 版病在哪：search 是哈希 O(L) 没问题，但 startsWith 每次都要遍历所有单词逐个 startsWith，O(N × L)。前缀查询是搜索引擎联想、路由匹配这类场景的核心操作，频率极高，O(N × L) 直接不可用。Trie 把「前缀」变成「树上的路径」：插入沿字母建节点，查前缀就是沿着路径走到底、中间断了就 false。看到「大量字符串 + 高频前缀查询」这个信号，就选 Trie——它的「按字符分叉」结构让前缀查询也降到 O(L)。

多解法对比

解法insert / searchstartsWith空间适用场景
HashSet 存单词O(L) / O(L)O(N × L)O(N × L)只查完整单词、几乎不查前缀
Trie 26 叉树（最优）O(L)O(L)O(26 × N × L)频繁前缀查询，标准答案

为什么选 Trie 为最优：这题的考察点就是「把 startsWith 从 O(N × L) 降到 O(L)」。虽然 Trie 在空间上（定长 26 数组）比 HashSet 略费，但在「海量字符串 + 高频前缀查询」的真实场景（输入法联想、路由、拼写提示）里，时间收益是决定性的。面试手撕默认写 Trie 版本。

CodeTop 变体

总结：四题四模板

题目核心模板一句话心法
200. 岛屿数量DFS 沉岛 / 连通块计数遇到 '1' 计数 +1，DFS 沉成 '0'
994. 腐烂的橘子多源 BFS 按层扩散所有源同时入队，层数 = 分钟数
207. 课程表Kahn 拓扑排序判环入度为 0 入队，count == V 则无环
208. 实现 Trie26 叉树 + end 标记插入建路径，查找看标记，前缀看路径

背熟这四套模板，Hot 100 图论篇手撕基本可以一把过。遇到变体题，先判断它落在哪个模板上，再套用对应的「现实类比」讲清楚思路，面试官要的往往就是那层「本质 + 类比」。

章末提问

  1. #200 为什么 DFS 沉岛用原矩阵当 visited，比单独 visited 数组好？缺点是什么？——结论：好省掉一整份 O(mn) 的 visited 数组、代码更短；缺点是会修改原矩阵，若不允许改输入就得退回 visited 数组，且全陆地的 DFS 会递归栈溢出、要换 BFS。
  2. #994 为什么「多源同时入队」的 BFS 一定给最短时间，逐个单源 BFS 再取 max 为什么不对？——结论：多源同时扩散才符合「所有烂橘子同一分钟一起传播」的语义，层数就是分钟数；逐个单源会大量重复访问、复杂度退化，且无法表达「同时」。
  3. #207 判环为什么用 count == numCourses 而不是看队列空不空？——结论：队列空只能说明「没有入度为 0 的点了」，但剩下的可能是一圈互相依赖的环。只有统计实际处理掉的课程数等于总数，才能区分「全处理完」和「剩下一圈环」。
Share this post on:
Share this post via WhatsAppShare this post on FacebookShare this post on XShare this post via TelegramShare this post on PinterestShare this post via email
Previous Post
LeetCode Hot 100——回溯篇（选择-递归-撤销、剪枝）
Next Post
LeetCode Hot 100——二叉树篇（遍历、深度、最近公共祖先）