基本题目

127. 单词接龙

BFS+字符串快速匹配 Trie

class Solution {
public:
    struct Trie {
        bool terminal = false;
        string word;
        unordered_map<char, Trie *> children;

        void addPath(const string &word) {
            Trie *tmp = this;
            for (const char c : word) {
                if (!tmp->children.count(c)) tmp->children[c] = new Trie();
                tmp = tmp->children[c];
            }
            tmp->terminal = true;
            tmp->word = word;
        }

        Trie *traverse(const string &word) {
            Trie *tmp = this;
            for (const char c : word) {
                if (!tmp->children.count(c)) return nullptr;
                tmp = tmp->children[c];
            }
            return tmp->terminal ? tmp : nullptr;
        }
    };

    unordered_set<string> searched;
    queue<string> q;

    int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
        Trie *trie = new Trie();
        for (const string &word : wordList) trie->addPath(word);
        if (beginWord == endWord && trie->traverse(endWord)) return 1;

        q.push(beginWord);
        searched.insert(beginWord);
        int dist = 2;
        while (!q.empty()) {
            // Mark all strings in the queue as searched
            // Add transformed words into the queue
            int m = q.size();
            for (int i = 0; i < m; i++) {
                string s = q.front();
                q.pop();

                Trie *tmp = trie, *leaf;
                for (int j = 0; j < s.size(); j++) {
                    // Change character s[j]
                    for (auto &[c, node] : tmp->children) {
                        if (c != s[j]) {
                            if ((leaf = node->traverse(s.substr(j + 1)))) {
                                if (leaf->word == endWord) return dist;
                                if (!searched.count(leaf->word)) {
                                    q.push(leaf->word);
                                    searched.insert(leaf->word);
                                }
                            }
                        }
                    }

                    // Move forward
                    if (tmp->children.count(s[j])) tmp = tmp->children[s[j]];
                    else break;
                }
            }
            dist++;
        }
        return 0;
    }
};

为了加快邻接节点搜索的速度（如果不使用 Trie，枚举速度较慢），可以引入带有 wildcard 的辅助接点，如 h_t。具体可参考[[Chapter17 复杂难度]]中的第 22 题

class Solution {
public:
    map<string, vector<string>> dict;
    unordered_set<string> searched;
    queue<string> q;

    int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
        for (const string &s : wordList) {
            for (int i = 0; i < s.size(); i++) {
                string tmp = s;
                tmp[i] = ' ';
                dict[tmp].push_back(s);
            }
        }

        q.push(beginWord);
        searched.insert(beginWord);
        int dist = 2;
        while (!q.empty()) {
            int m = q.size();
            for (int i = 0; i < m; i++) {
                string s = q.front();
                q.pop();
                for (int j = 0; j < s.size(); j++) {
                    string tmp = s;
                    tmp[j] = ' ';
                    for (const string &s : dict[tmp]) {
                        if (!searched.count(s)) {
                            if (s == endWord) return dist;
                            q.push(s);
                            searched.insert(s);
                        }
                    }
                }
            }
            dist++;
        }
        return 0;
    }
};

841. 钥匙和房间

BFS 扩展连通图

class Solution {
public:
    bool canVisitAllRooms(vector<vector<int>>& rooms) {
        int n = rooms.size();
        vector<bool> unlocked(n, false);

        queue<int> q;
        unlocked[0] = true;
        q.push(0);
        while (!q.empty()) {
            int r = q.front();
            q.pop();
            for (const int &k : rooms[r]) {
                if (!unlocked[k]) {
                    unlocked[k] = true;
                    q.push(k);
                }
            }
        }

        for (const bool &t : unlocked)
            if (!t) return false;
        return true;
    }
};

还可以使用计数器来判断合法条件

class Solution {
public:
    bool canVisitAllRooms(vector<vector<int>>& rooms) {
        int n = rooms.size();
        vector<bool> unlocked(n, false);

        queue<int> q;
        unlocked[0] = true;
        q.push(0);
        int count = 1;
        while (!q.empty()) {
            int r = q.front();
            q.pop();
            for (const int &k : rooms[r]) {
                if (!unlocked[k]) {
                    unlocked[k] = true;
                    q.push(k);
                    count++;
                }
            }
        }

        return count == n;
    }
};

463. 岛屿的周长

根据周围的陆地格数，更新周长值

class Solution {
public:
    int islandPerimeter(vector<vector<int>>& grid) {
        int m = grid.size(), n = grid[0].size();
        int result = grid[0][0] ? 4 : 0;
        for (int i = 1; i < m; i++)
            if (grid[i][0]) result += grid[i - 1][0] ? 2 : 4;
        for (int j = 1; j < n; j++)
            if (grid[0][j]) result += grid[0][j - 1] ? 2 : 4;
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                if (grid[i][j]) {
                    result += 4;
                    if (grid[i - 1][j]) result -= 2;
                    if (grid[i][j - 1]) result -= 2;
                }
            }
        }
        return result;
    }
};

1971. 寻找图中是否存在路径

并查集

class Solution {
public:
    int findRoot(const vector<int> &parent, int p) {
        while (parent[p] >= 0) p = parent[p];
        return p;
    }

    bool validPath(int n, vector<vector<int>>& edges, int source, int destination) {
        vector<int> parent(n, -1);
        for (const vector<int> &e : edges) {
            int p1 = findRoot(parent, e[0]), p2 = findRoot(parent, e[1]);
            if (p1 != p2) parent[p1] = p2;
        }
        return findRoot(parent, source) == findRoot(parent, destination);
    }
};

也可使用 DFS、BFS 直接搜索

684. 冗余连接

冗余边的另一种描述方式：冗余边的两个节点已经联通，属于同一并查集

class Solution {
public:
    int findRoot(const vector<int> &parent, int p) {
        while (parent[p] >= 0) p = parent[p];
        return p;
    }

    vector<int> findRedundantConnection(vector<vector<int>>& edges) {
        int n = edges.size();
        vector<int> parent(n + 1, -1);
        for (const vector<int> &e : edges) {
            int p1 = findRoot(parent, e[0]), p2 = findRoot(parent, e[1]);
            if (p1 == p2) return e;
            else parent[p1] = p2;
        }
        return {};
    }
};

685. 冗余连接 II

可能存在的冲突点：多重父节点（追踪各节点的父节点）、环路（并查集），针对不同情况讨论

class Solution {
public:
    int findRoot(const vector<int> &parent, int p) {
        while (parent[p] >= 0) p = parent[p];
        return p;
    }

    vector<int> findRedundantDirectedConnection(vector<vector<int>>& edges) {
        int n = edges.size();
        vector<int> parent(n + 1, -1);
        vector<int> treeParent(n + 1, -1);
        vector<int> conflict, cycle;
        bool hasConflict = false, hasCycle = false;

        for (const vector<int> &e : edges) {
            if (treeParent[e[1]] >= 0) {
                // Already has a parent: mark as a conflict
                hasConflict = true;
                conflict = e;
            }
            else {
                treeParent[e[1]] = e[0];

                int p1 = findRoot(parent, e[0]), p2 = findRoot(parent, e[1]);
                if (p1 == p2) {
                    // A new cycle has formed: mark as cycle
                    hasCycle = true;
                    cycle = e;
                }
                else {
                    parent[p1] = p2;
                }
            }
        }
        
        // An edge from a inner node to the root forms a cycle
        if (!hasConflict) return cycle;

        // No cycles detected: remove the last conflicting edge
        if (!hasCycle) return conflict;

        // Cycle & conclict: the conflicting edge in the cycle should be removed
        // Select one from (u,v) and (parent[v],v)
        // If (u,v) is the answer, considering it is not added in the algorithm,
        // no cycles would be formed. So (parent[v],v) is the edge to be removed.
        return {treeParent[conflict[1]], conflict[1]};
    }
};