图论算法

200. 岛屿数量

c++

class Solution {
public:
    int numIslands(vector<vector<char>>& grid) {
        int cnt = 0;
        for (int i = 0; i < grid.size(); ++i) {
            for (int j = 0; j < grid[0].size(); ++j) {
                if (grid[i][j] == '1') {
                    ++cnt;
                    dfs(grid, i, j, cnt);
                }
            }
        }
        return cnt;
    }

    void dfs(vector<vector<char>>& grid, int r, int c, int& cnt) {
        if (!inGrid(grid, r, c)) {
            return;
        }
        if (grid[r][c] != '1') {
            return;
        }
        grid[r][c] = '2';
        dfs(grid, r - 1, c, cnt);
        dfs(grid, r + 1, c, cnt);
        dfs(grid, r, c - 1, cnt);
        dfs(grid, r, c + 1, cnt);
    }
    bool inGrid(vector<vector<char>>& grid, int r, int c) {
        if (r >= 0 && r < grid.size() && c >= 0 && c < grid[0].size()) {
            return true;
        }
        return false;
    }
};

c++

class Solution {
public:
    int maxAreaOfIsland(vector<vector<int>>& grid) {
        int ret = 0;
        for (int i = 0; i < grid.size(); ++i) {
            for (int j = 0; j < grid[0].size(); ++j) {
                if (grid[i][j] == 1) {
                    ret = max(ret, dfs(grid, i, j));
                }
            }
        }
        return ret;
    }
    int dfs(vector<vector<int>>& grid, int r, int c) {
        if (!inGrid(grid, r, c)) {
            return 0;
        }
        if (grid[r][c] != 1) {
            return 0;
        }
        grid[r][c] = 2;
        return 1 + dfs(grid, r - 1, c) + dfs(grid, r + 1, c) + dfs(grid, r, c - 1) + dfs(grid, r, c + 1);
    }
    bool inGrid(vector<vector<int>>& grid, int r, int c) {
        if (r >= 0 && r < grid.size() && c >= 0 && c < grid[0].size()) {
            return true;
        }
        return false;
    }
};

c++

class Solution {
public:
    // https://leetcode.cn/problems/making-a-large-island/solutions/1830957/by-muse-77-37hi/
    int largestIsland(vector<vector<int>>& grid) {
        int ret = 0;
        int index = 2;
        for (int i = 0; i < grid.size(); ++i) {
            for (int j = 0; j < grid[0].size(); ++j) {
                if (grid[i][j] == 1) {
                    int area = getArea(grid, i, j, index);
                    m_[index++] = area;
                }
            }
        }
        for (int i = 0; i < grid.size(); ++i) {
            for (int j = 0; j < grid[0].size(); ++j) {
                if (grid[i][j] == 0) {
                    set<int> s = getIndexSet(grid, i, j);
                    int tmp = 1;
                    for (int e : s) {
                        tmp += m_[e];
                    }
                    ret = max(ret, tmp);
                }
            }
        }
        return ret == 0 ? m_[2] : ret;
    }
private:
    set<int> getIndexSet(vector<vector<int>>& grid, int r, int c) {
        set<int> ret;
        if (inGrid(grid, r - 1, c) && grid[r - 1][c] != 0) {
            ret.insert(grid[r - 1][c]);
        }
        if (inGrid(grid, r + 1, c) && grid[r + 1][c] != 0) {
            ret.insert(grid[r + 1][c]);
        }
        if (inGrid(grid, r, c - 1) && grid[r][c - 1] != 0) {
            ret.insert(grid[r][c - 1]);
        }
        if (inGrid(grid, r, c + 1) && grid[r][c + 1] != 0) {
            ret.insert(grid[r][c + 1]);
        }
        return ret;
    }
    int getArea(vector<vector<int>>& grid, int r, int c, int index) {
        if (!inGrid(grid, r, c)) {
            return 0;
        }
        if (grid[r][c] != 1) {
            return 0;
        }
        grid[r][c] = index;
        return 1 + getArea(grid, r - 1, c, index) + getArea(grid, r + 1, c, index) + getArea(grid, r, c - 1, index) + getArea(grid, r, c + 1, index);
    }
    bool inGrid(vector<vector<int>>& grid, int r, int c) {
        if (r >= 0 && r < grid.size() && c >= 0 && c < grid[0].size()) {
            return true;
        }
        return false;
    }
private:
    unordered_map<int, int> m_;
};

c++

class Solution {
public:
    int islandPerimeter(vector<vector<int>>& grid) {
        #if 0
        int land = 0;
        int board = 0;
        for (int i = 0; i < grid.size(); ++i) {
            for (int j = 0; j < grid[0].size(); ++j) {
                if (grid[i][j] == 1) {
                    ++land;
                    if (i < grid.size() - 1 && grid[i + 1][j] == 1) {
                        ++board;
                    }
                    if (j < grid[0].size() - 1 && grid[i][j + 1] == 1) {
                        ++board;
                    }
                }
            }
        }
        return 4 * land - 2 * board;
        #endif
        int ret = 0;
        for (int i = 0; i < grid.size(); ++i) {
            for (int j = 0; j < grid[0].size(); ++j) {
                if (grid[i][j] == 1) {
                    dfs(grid, i, j, ret);
                    break;
                }
            }
        }
        return ret;
    }
private:
    void dfs(vector<vector<int>>& grid, int r, int c, int& ret) {
        if (!inGrid(grid, r, c) || grid[r][c] == 0) {
            ++ret;
            return;
        }
        if (grid[r][c] != 1) {
            return;
        }
        grid[r][c] = 2;
        dfs(grid, r - 1, c, ret);
        dfs(grid, r + 1, c, ret);
        dfs(grid, r, c - 1, ret);
        dfs(grid, r, c + 1, ret);
    }
    bool inGrid(vector<vector<int>>& grid, int r, int c) {
        if (r >= 0 && r < grid.size() && c >= 0 && c < grid[0].size()) {
            return true;
        }
        return false;
    }
};

1020

c++

class Solution {
public:
    int numEnclaves(vector<vector<int>>& grid) {
        int ret = 0;
        int m = grid.size();
        int n = grid[0].size();
        queue<vector<int>> q;
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (i * j == 0 || i == m - 1 || j == n - 1) {
                    // ++ret;
                    q.push({i, j});
                }
            }
        }

        while (!q.empty()) {
            vector<int> tmp = q.front();
            q.pop();
            int r = tmp[0];
            int c = tmp[1];
            if (r < 0 || r > m - 1 | c < 0 || c > n - 1 || grid[r][c] != 1) {
                continue;
            }
            grid[r][c] = 0;
            // --ret;
            q.push({r - 1, c});
            q.push({r + 1, c});
            q.push({r, c - 1});
            q.push({r, c + 1});
        }

        for (int i = 0; i < grid.size(); ++i) {
            for (int j = 0; j < grid[0].size(); ++j) {
                if (grid[i][j] == 1) {
                    ++ret;
                }
            }
        }

        return ret;
    }
#if 0
    int numEnclaves(vector<vector<int>>& grid) {
        int cnt = 0;
        for (int i = 0; i < grid.size(); ++i) {
            for (int j = 0; j < grid[0].size(); ++j) {
                if (i * j == 0 || i == grid.size() - 1 || j == grid[0].size() - 1) {
                    dfs(grid, i, j);
                }
            }
        }
        
        for (int i = 0; i < grid.size(); ++i) {
            for (int j = 0; j < grid[0].size(); ++j) {
                if (grid[i][j] == 1) {
                    ++cnt;
                }
            }
        }
        return cnt;
    }

private:
    void dfs(vector<vector<int>>& grid, int r, int c) {
        if (!isValid(grid, r, c) || grid[r][c] == 0) {
            return;
        }
        grid[r][c] = 0;
        dfs(grid, r - 1, c);
        dfs(grid, r + 1, c);
        dfs(grid, r, c - 1);
        dfs(grid, r, c + 1);
    }

    bool isValid(vector<vector<int>>& grid, int r, int c) {
        if (r >= 0 && r < grid.size() && c >= 0 && c < grid[0].size()) {
            return true;
        }
        return false;
    }
#endif
};

417

c++

[1,2,2,3,5]
[3,2,3,4,4]
[2,4,5,3,1]
[6,7,1,4,5]
[5,1,1,2,4]

每一个 cell 有四个可能的流向
这个问题的关键在于确定哪些单元格可以同时被太平洋和大西洋访问到。为了解决这个问题，我们可以使用深度优先搜索（DFS）来遍历矩阵，并标记从每个单元格开始可以到达的所有单元格。我们可以从太平洋和大西洋分别开始进行搜索。

从边界开始搜索：我们从矩阵的四个边界开始搜索。对于太平洋来说，我们从左边界和顶部边界开始搜索；对于大西洋来说，我们从右边界和底部边界开始搜索。
深度优先搜索：从边界上的每个单元格开始，我们使用深度优先搜索来遍历与当前单元格相邻且海拔高度不高于当前单元格的所有单元格。我们只能向海拔不高的方向流动。我们使用递归或显式的栈来实现深度优先搜索。
标记可到达的单元格：我们使用两个矩阵来记录哪些单元格可以到达太平洋和大西洋。我们分别使用两个矩阵canReachPacific和canReachAtlantic来记录从边界出发可以到达的单元格。在搜索过程中，我们标记所有可到达的单元格。
找到共同可到达的单元格：最后，我们找到那些既能到达太平洋又能到达大西洋的单元格，这些单元格的坐标即是我们要找到的结果。

c++

class Solution {
public:
    vector<vector<int>> pacificAtlantic(vector<vector<int>>& heights) {
        vector<vector<int>> ret;
        if (heights.empty()) {
            return ret;
        }

        int m = heights.size();
        int n = heights[0].size();
        vector<vector<bool>> canReachPacific(m, vector<bool>(n, false));
        vector<vector<bool>> canReachAtlantic(m, vector<bool>(n, false));

        for (int i = 0; i < m; ++i) {
            // dfs(heights, canReachPacific, i, 0);
            // dfs(heights, canReachAtlantic, i, n - 1);
            dfsV2(heights, canReachPacific, i, 0);
            dfsV2(heights, canReachAtlantic, i, n - 1);
        }
        for (int j = 0; j < n; ++j) {
            // dfs(heights, canReachPacific, 0, j);
            // dfs(heights, canReachAtlantic, m - 1, j);
            dfsV2(heights, canReachPacific, 0, j);
            dfsV2(heights, canReachAtlantic, m - 1, j);
        }

        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (canReachPacific[i][j] && canReachAtlantic[i][j]) {
                    ret.push_back({i, j});
                }
            }
        }

        return ret;
    }

private:
    void dfs(vector<vector<int>>& heights, vector<vector<bool>>& visited, int i, int j) {
        if (!isValid(heights, i, j)) {
            return;
        }
        visited[i][j] = true;
        if (isValid(heights, i - 1, j) && !visited[i - 1][j] && heights[i - 1][j] >= heights[i][j]) {
            dfs(heights, visited, i - 1, j);
        }
        if (isValid(heights, i + 1, j) && !visited[i + 1][j] && heights[i + 1][j] >= heights[i][j]) {
            dfs(heights, visited, i + 1, j);
        }
        if (isValid(heights, i, j - 1) && !visited[i][j - 1] && heights[i][j - 1] >= heights[i][j]) {
            dfs(heights, visited, i, j - 1);
        }
        if (isValid(heights, i, j + 1) && !visited[i][j + 1] && heights[i][j + 1] >= heights[i][j]) {
            dfs(heights, visited, i, j + 1);
        }
    }

    bool isValid(vector<vector<int>>& heights, int i, int j) {
        if (i >= 0 && i < heights.size() && j >= 0 && j < heights[0].size()) {
            return true;
        }
        return false;
    }

    void dfsV2(vector<vector<int>>& heights, vector<vector<bool>>& visited, int i, int j) {
        visited[i][j] = true;
        static vector<pair<int,int>> directions = {{-1,0},{1,0},{0,-1},{0,1}};
        for (const auto& dir : directions) {
            // next i
            int ni = i + dir.first;
            // next j
            int nj = j + dir.second;
            if (ni >= 0 && ni < heights.size() && nj >= 0 && nj < heights[0].size()
            && heights[ni][nj] >= heights[i][j] && !visited[ni][nj]) {
                dfs(heights,visited,ni,nj);
            }
        }
    }
};

127 单词接龙

字典 wordList 中从单词 beginWord和 endWord 的 转换序列 是一个按下述规格形成的序列 beginWord -> s(1) -> s(2) -> ... -> s(k)：

每一对相邻的单词只差一个字母。
对于 1 <= i <= k 时，每个 s(i) 都在 wordList 中。注意， beginWord不需要在 wordList 中。
s(k) == endWord

给你两个单词beginWord和 endWord 和一个字典 wordList ，返回从 beginWord 到 endWord 的 最短转换序列 中的 单词数目 。如果不存在这样的转换序列，返回 0 。

示例 1：

输入：beginWord = "hit"， endWord = "cog"， wordList = ["hot"，"dot"，"dog"，"lot"，"log"，"cog"] 输出：5 解释：一个最短转换序列是 "hit" -> "hot" -> "dot" -> "dog" -> "cog"，返回它的长度 5。

示例 2：

输入：beginWord = "hit"， endWord = "cog"， wordList = ["hot"，"dot"，"dog"，"lot"，"log"] 输出：0 解释：endWord "cog" 不在字典中，所以无法进行转换。

思路

使用 BFS

将 beginWord 放入队列中
如果队列不空，循环队列
1. 出队一个 curWord
2. 遍历 curWord 的每一个字符，尝试在 wordList 中匹配
  1. 匹配到了 endWord，得到了最终答案
  2. 匹配到了某个 word，把这个 word 入队
  3. 没匹配到，继续循环
3. 增加计数器
返回计数器的值

实现

c++

class Solution {
public:
    int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
        // 构建字典，方便快速查找
        unordered_set<string> dic(wordList.begin(), wordList.end());
         // 如果目标单词不在字典中，则无法转换，直接返回0
        if(dic.count(endWord) == 0) {
            return 0;
        }

        unordered_set<string> visited;
        visited.insert(beginWord);

        queue<string> q;
        q.push(beginWord);
        // 起始单词算一步
        int ret = 1;
        while (!q.empty())
        {   
            // 获取这一层的大小
            int s = q.size();
            // 遍历这一层中的所有单词
            for (int i = 0; i < s; ++i) {
                string curWord = q.front();
                q.pop();
                // 对当前位置的字母进行替换
                for (int j = 0; j < curWord.size(); ++j) {
                    char oriChar = curWord[j];
                    for (char c = 'a'; c <= 'z'; ++c) {
                        if (curWord[j] == c) {
                            continue;
                        }
                        curWord[j] = c;
                        // 如果新单词在字典中并且未访问过
                        if (dic.count(curWord) && !visited.count(curWord)) {
                            if (curWord == endWord) {
                                return ret + 1;
                            }
                            q.push(curWord);
                            visited.insert(curWord);
                        }
                    }
                    // 恢复当前位置的字母，以便尝试下一个位置
                    curWord[j] = oriChar;
                }
            }
            // 走完一轮相邻单词，步数加1
            ++ret;
        }
        // 如果队列为空仍未找到目标单词，则返回0
        return 0;
    }
};

797. 所有可能的路径

给你一个有 n 个节点的 有向无环图（DAG），请你找出所有从节点 0 到节点 n-1 的路径并输出（不要求按特定顺序）

graph[i] 是一个从节点 i 可以访问的所有节点的列表（即从节点 i 到节点 graph[i][j]存在一条有向边）。

c++

class Solution {
public:
    vector<vector<int>> allPathsSourceTarget(vector<vector<int>>& graph) {
        vector<int> path;
        // 要有这一步
        path.push_back(0);
        vector<vector<int>> ret;
        dfs(graph, 0, path, ret);
        return ret;
    }

    void dfs(vector<vector<int>>& graph, int node, vector<int>& path, vector<vector<int>>& ret) {
        if (node == graph.size() - 1) {
            ret.push_back(path);
            return;
        }
        for (int i = 0; i < graph[node].size(); ++i) {
            path.push_back(graph[node][i]);
            dfs(graph, graph[node][i], path, ret);
            path.pop_back();
        }
    }
};

200. 岛屿数量

给你一个由 '1'（陆地）和 '0'（水）组成的的二维网格，请你计算网格中岛屿的数量。

岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。

此外，你可以假设该网格的四条边均被水包围。

思路
- 遍历grid，对'1'的网格进行遍历，增加统计计数
- 遍历使用bfs或者dfs，对访问过的网格进行标记
岛屿问题参考
- https://leetcode.cn/problems/number-of-islands/solutions/211211/dao-yu-lei-wen-ti-de-tong-yong-jie-fa-dfs-bian-li-
dfs
- 复杂度分析
  - 时间复杂度：O(MN)，其中 M 和 N 分别为行数和列数。
  - 空间复杂度：O(MN)，在最坏情况下，整个网格均为陆地，深度优先搜索的深度达到 MN。

c++

class Solution {
public:
    int numIslands(vector<vector<char>>& grid) {
        int ret = 0;
        for (int i = 0; i < grid.size(); ++i) {
            for (int j = 0; j < grid[0].size(); ++j) {
                if (grid[i][j] == '1') {
                    dfs(grid, i, j); 
                    ++ret;
                }
            }
        }
        return ret;
    }
    void dfs(vector<vector<char>>& grid, int x, int y) {
        // 先做有效性判断
        if (!isValid(grid, x, y)) {
            return;
        }
        if (grid[x][y] != '1') {
            return;
        }
        grid[x][y] = '2';
        dfs(grid, x - 1, y);
        dfs(grid, x + 1, y);
        dfs(grid, x, y - 1);
        dfs(grid, x, y + 1);
    }
    bool isValid(vector<vector<char>>& grid, int x, int y) {
        return x >= 0 && x < grid.size() && y >= 0 && y < grid[0].size();
    }
};

bfs
- 复杂度分析
  - 时间复杂度：O(MN)，其中 M 和 N 分别为行数和列数。
  - 空间复杂度：O(min(M,N))，在最坏情况下，整个网格均为陆地，队列的大小可以达到 min(M,N)。

c++

class Solution {
public:
    int numIslands(vector<vector<char>>& grid) {
        int ret = 0;
        for (int i = 0; i < grid.size(); ++i) {
            for (int j = 0; j < grid[0].size(); ++j) {
                if (grid[i][j] == '1') {
                    bfs(grid, i, j); 
                    ++ret;
                }
            }
        }
        return ret;
    }
    void bfs(vector<vector<char>>& grid, int x, int y) {
        queue<pair<int,int>> que;
        que.push({x, y});
        while (!que.empty()) {
            auto point = que.front();
            que.pop();
            int nx = point.first;
            int ny = point.second;
            // timeout
            // grid[nx][ny] = '2'
            if (isValid(grid, nx - 1, ny) && grid[nx - 1][ny] == '1') {
                grid[nx - 1][ny] = '2';
                que.push({nx - 1, ny});
            } 
            if (isValid(grid, nx + 1, ny) && grid[nx + 1][ny] == '1') {
                grid[nx + 1][ny] = '2';
                que.push({nx + 1, ny});
            } 
            if (isValid(grid, nx, ny - 1) && grid[nx][ny - 1] == '1') {
                grid[nx][ny - 1] = '2';
                que.push({nx, ny - 1});
            } 
            if (isValid(grid, nx, ny + 1) && grid[nx][ny + 1] == '1') {
                grid[nx][ny + 1] = '2';
                que.push({nx, ny + 1});
            } 
        }
    }
    bool isValid(vector<vector<char>>& grid, int x, int y) {
        return x >= 0 && x < grid.size() && y >= 0 && y < grid[0].size();
    }
};

994. 腐烂的橘子

在给定的 m x n 网格 grid 中，每个单元格可以有以下三个值之一：

值 0 代表空单元格；
值 1 代表新鲜橘子；
值 2 代表腐烂的橘子。

每分钟，腐烂的橘子 周围 4 个方向上相邻 的新鲜橘子都会腐烂。

返回 直到单元格中没有新鲜橘子为止所必须经过的最小分钟数。如果不可能，返回 -1 。

c++

/*
通过bfs模拟腐烂过程

统计新鲜橘子的数量
将腐烂的橘子放入队列

*/
class Solution {
public:
    int orangesRotting(vector<vector<int>>& grid) {
        // row size
        int m = grid.size();
        // col size
        int n = grid[0].size();

        // 统计新鲜橘子数量
        int fresh_count = 0;
        // 统计时间
        int minutes = 0;

        queue<pair<int, int>> que;

        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                // 新鲜橘子
                if (grid[i][j] == 1) {
                    ++fresh_count;
                // 腐烂橘子
                } else if (grid[i][j] == 2) {
                    que.push({i, j});
                } else {
                    // do nothing
                }
            }
        }

        vector<pair<int, int>> directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

        while (!que.empty() && fresh_count > 0) {
            // 注意变量命名，这里不要再用n
            int que_size = que.size();
            ++minutes;
            // 出队操作要在这个小循环里面
            for (int i = 0; i < que_size; ++i) {
                pair<int, int> point = que.front();
                que.pop();
                int x = point.first;
                int y = point.second;
                for (auto p : directions) {
                    int nx = x + p.first;
                    int ny = y + p.second;
                    if (nx >= 0 && nx < m && ny >= 0 && ny < n && grid[nx][ny] == 1) {
                        --fresh_count;
                        grid[nx][ny] = 2;
                        que.push({nx, ny});
                    }
                }
            }
        }

        return fresh_count == 0 ? minutes : -1;
    }
};

207. 课程表

你这个学期必须选修 numCourses 门课程，记为 0 到 numCourses - 1 。

在选修某些课程之前需要一些先修课程。先修课程按数组 prerequisites 给出，其中 prerequisites[i] = [a(i), b(i)] ，表示如果要学习课程 a(i) 则必须先学习课程 b(i)（）。

例如，先修课程对 [0, 1] 表示：想要学习课程 0 ，你需要先完成课程 1 。

请你判断是否可能完成所有课程的学习？如果可以，返回 true ；否则，返回 false 。

思路
- 理解什么是拓扑排序
- 会构建入度数组和邻接表

c++

/*
拓扑排序（Kahn's Algorithm）
拓扑排序是一种针对有向无环图（DAG, Directed Acyclic Graph）的排序算法，
能够将图中的节点排序，使得对于每一条有向边 (u, v)，节点 u 在节点 v 之前。
若图中有环，则无法进行拓扑排序。
*/
class Solution {
public:
    bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
        // 初始化入度数组
        vector<int> in_degree(numCourses, 0);
        // 初始化邻接表
        vector<vector<int>> adj_list(numCourses);
        // 填充入度数组和邻接表
        for (int i = 0; i < prerequisites.size(); ++i) {
            in_degree[prerequisites[i][0]]++;
            adj_list[prerequisites[i][1]].push_back(prerequisites[i][0]);
        }
        // 初始化队列，将入度为0的节点入队
        queue<int> que;
        for (int i = 0; i < in_degree.size(); ++i) {
            if (in_degree[i] == 0) {
                que.push(i);
            }
        }
        // 用于记录访问过的节点数
        int visited = 0;
        
        while (!que.empty()) {
            int course = que.front();
            que.pop();
            ++visited;
            // 遍历与当前课程相连的所有课程
            for (int next_course : adj_list[course]) {
                in_degree[next_course]--;
                if (in_degree[next_course] == 0) {
                    que.push(next_course);
                } 
            }
        }
        // 如果访问的节点数等于课程总数，则可以完成所有课程
        return visited == numCourses;
    }
};

208. 实现 Trie (前缀树)

Trie（发音类似 "try"）或者说 前缀树 是一种树形数据结构，用于高效地存储和检索字符串数据集中的键。这一数据结构有相当多的应用情景，例如自动补全和拼写检查。

请你实现 Trie 类：

Trie() 初始化前缀树对象。
void insert(String word) 向前缀树中插入字符串 word 。
boolean search(String word) 如果字符串 word 在前缀树中，返回 true（即，在检索之前已经插入）；否则，返回 false 。
boolean startsWith(String prefix) 如果之前已经插入的字符串 word 的前缀之一为 prefix ，返回 true ；否则，返回 false 。
参考
- https://leetcode.cn/problems/implement-trie-prefix-tree/solutions/98390/trie-tree-de-shi-xian-gua-he-chu-xue-zhe-by-huwt

c++

class Trie {
public:
    Trie() {
        root = new TrieNode();
    }
    
    void insert(string word) {
        TrieNode* node = root;
        for (char c : word) {
            if (node->children.count(c) == 0) {
                node->children[c] = new TrieNode();
            }
            node = node->children[c];
        }
        node->is_end = true;
    }
    
    bool search(string word) {
        TrieNode* node = root;
        for (char c : word) {
            if (!node->children.count(c)) {
                return false;
            }
            node = node->children[c];
        }
        return node->is_end;
    }
    
    bool startsWith(string prefix) {
        TrieNode* node = root;
        for (char c : prefix) {
            if (!node->children.count(c)) {
                return false;
            }
            node = node->children[c];
        }
        return true;
    }
private:
    struct TrieNode {
        bool is_end;
        unordered_map<char, TrieNode*> children;
        TrieNode() : is_end(false) {}
    };
private:
    TrieNode* root; 
};

/**
 * Your Trie object will be instantiated and called as such:
 * Trie* obj = new Trie();
 * obj->insert(word);
 * bool param_2 = obj->search(word);
 * bool param_3 = obj->startsWith(prefix);
 */

图论算法 ​

200. 岛屿数量 ​

417 ​

127 单词接龙 ​

797. 所有可能的路径 ​

200. 岛屿数量 ​

994. 腐烂的橘子 ​

207. 课程表 ​

208. 实现 Trie (前缀树) ​

图论算法

200. 岛屿数量

417

127 单词接龙

797. 所有可能的路径

200. 岛屿数量

994. 腐烂的橘子

207. 课程表

208. 实现 Trie (前缀树)