LeetCode HOT100 - 实现 Trie (前缀树)

板子，但是得自己写板子（）

具体介绍就不过多介绍了，放一下代码

class Trie {
private:
    struct Node {
        Node* next[26];
        bool isEnd;
        Node() : isEnd(false) {
            for (int i = 0; i < 26; i++) {
                next[i] = nullptr;
            }
        }
    };
    Node* root;

public:
    Trie() {
        root = new Node();
    }
    void insert(string word) {
        Node* p = root;
        for (char c : word) {
            int idx = c - 'a';
            if (p->next[idx] == nullptr) {
                p->next[idx] = new Node();
            }
            p = p->next[idx];
        }
        p->isEnd = true;
    }
    bool search(string word) {
        Node* p = root;
        for (char c : word) {
            int idx = c - 'a';
            if (p->next[idx] == nullptr) {
                return false;
            }
            p = p->next[idx];
        }
        return p->isEnd;
    }
    bool startsWith(string prefix) {
        Node* p = root;
        for (char c : prefix) {
            int idx = c - 'a';
            if (p->next[idx] == nullptr) {
                return false;
            }
            p = p->next[idx];
        }
        return true;
    }
};

/**
 * 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);
 */

以及 https://chuna2.787528.xyz/WIDA/p/17633758.html 中哥哥的代码

/**   字典树 Trie
 *    2023-09-26: https://qoj.ac/submission/188957
**/
constexpr i64 inf = 1E18;

constexpr int N = 1E6 + 10;

int trie[N][26];
int tot;

int newNode() {
    tot++;
    std::fill(trie[tot], trie[tot] + 26, 0);
    val[tot] = inf;
    return tot;
}

void solve() {
    //* init
    tot = 0;
    newNode();

    //* insert
    for (int i = 0; i < N; i++) { 
        int p = 1;
        int l = S[i].size();
        for (int j = 0; j < l; j++) {
            int x = S[i][j] - 'a';
            if (!trie[p][x]) {
                trie[p][x] = newNode();
            }
            p = trie[p][x];
            //* 处理
            //* val[p] = std::min(val[p], l + K + f[(K - (l - j - 1) % K) % K]);
        }
    }
    
    //* query
    for (int i = 0; i < L; i++) {
        int p = 1;
        for (int j = i; j < L; j++) {
            int x = T[j] - 'a';
            p = trie[p][x];
            if (!p) {
                continue;
            }
            //* 处理
            //* dp[j + 1] = std::min(dp[j + 1], dp[i] + val[p]);
        }
    }
}

/**   字典树 Trie
 *    2024-06-18: https://cf.dianhsu.com/gym/105222/submission/266217560?version=1.5
**/
int tot;
int trie[N][2];
int f[N];

int newNode() {
    int x = ++tot;
    trie[x][0] = trie[x][1] = 0;
    f[x] = inf;
    return x;
}
void add(int x, int i) {
    int p = 1;
    for (int j = 29; j >= 0; j--) {
        int &q = trie[p][x >> j & 1];
        if (q == 0) {
            q = newNode();
        }
        p = q;
        f[p] = std::min(f[p], i);
    }
}

int query(int a, int b) {
    int ans1 = inf, ans2 = inf;
    int p = 1;
    for (int i = 29; i >= 0; i--) {
        int d = a >> i & 1;
        int e = b >> i & 1;
        if (e) {
            ans1 = std::min(ans1, f[trie[p][d]]);
        } else {
            ans2 = std::min(ans2, f[trie[p][d ^ 1]]);
        }
        p = trie[p][e ^ d];
    }
    ans1 = std::min(ans1, f[p]);
    ans2 = std::min(ans2, f[p]);
    if (ans1 == inf || ans2 == inf) {
        return -1;
    }
    return std::max({1, ans1, ans2});
}

/**   字典树 Trie
 *    2024-06-03: https://codeforces.com/contest/1980/submission/263960334
**/
int trie[N][2];
int cnt[N][2];
 
int tot = 0;
int newNode() {
    int x = ++tot;
    trie[x][0] = trie[x][1] = 0;
    cnt[x][0] = cnt[x][1] = 0;
    return x;
}
 
void add(int x, int d, int t = 1) {
    int p = 1;
    cnt[p][d] += t;
    for (int i = 29; i >= 0; i--) {
        int u = x >> i & 1;
        if (!trie[p][u]) {
            trie[p][u] = newNode();
        }
        p = trie[p][u];
        cnt[p][d] += t;
    }
}
 
int query(int x, int d) {
    int p = 1;
    if (!cnt[p][d]) {
        return 0;
    }
    int ans = 0;
    for (int i = 29; i >= 0; i--) {
        int u = x >> i & 1;
        if (cnt[trie[p][u ^ 1]][d]) {
            ans |= 1 << i;
            p = trie[p][u ^ 1];
        } else {
            p = trie[p][u];
        }
    }
    return ans;
}

/**   字典树 Trie
 *    2024-06-18: https://cf.dianhsu.com/gym/105222/submission/266217560
 *    2024-06-04: https://codeforces.com/contest/1980/submission/263960334
**/
constexpr int N = 1E7;
constexpr int inf = 1E9;
int tot;
int trie[N][2];
int f[N];

int newNode() {
    int x = ++tot;
    trie[x][0] = trie[x][1] = 0;
    f[x] = inf;
    return x;
}
void add(int x, int i) {
    int p = 1;
    for (int j = 29; j >= 0; j--) {
        int &q = trie[p][x >> j & 1];
        if (q == 0) {
            q = newNode();
        }
        p = q;
        f[p] = std::min(f[p], i);
    }
}

int query(int a, int b) {
    int ans1 = inf, ans2 = inf;
    int p = 1;
    for (int i = 29; i >= 0; i--) {
        int d = a >> i & 1;
        int e = b >> i & 1;
        if (e) {
            ans1 = std::min(ans1, f[trie[p][d]]);
        } else {
            ans2 = std::min(ans2, f[trie[p][d ^ 1]]);
        }
        p = trie[p][e ^ d];
    }
    ans1 = std::min(ans1, f[p]);
    ans2 = std::min(ans2, f[p]);
    if (ans1 == inf || ans2 == inf) {
        return -1;
    }
    return std::max({1, ans1, ans2});
}