undefined

Trie树

也叫“字典树”。它是一个树形结构。它是一种专门处理字符串匹配的数据结构，用来解决在一组字符串集合中快速查找某个字符串的问题。

Trie 树的本质，就是利用字符串之间的公共前缀，将重复的前缀合并在一起

class Trie {
public:
    char data{};
    Trie* node[26]{};
public:
    explicit Trie(char value) : data(value) {
        for (auto & i : node) {
            i = nullptr;
        }
    }
};

void printTrie(Trie* trie) {
    for (int i = 0; i < 26; i++) {
        if (trie->node[i] != nullptr) {
            std::cout << char(i+'a') << " ";
        }
    }
    std::cout << std::endl;
}

void insertTrie(Trie* trie, const std::string& str) {
    for (auto& x : str) {
        int pos = x-'a';
        if (trie->node[pos] == nullptr) {
            trie->node[pos] = new Trie(x);
        }
        trie = trie->node[pos];
    }
}

bool findStr(Trie* trie, const std::string& str) {
    for (auto& x : str) {
        int pos = x-'a';
        if (trie->node[pos] == nullptr) {
            return false;
        }
        trie = trie->node[pos];
    }
    return true;
}

构建 Trie 树的过程，需要扫描所有的字符串，时间复杂度是 O(n)（n 表示所有字符串的长度和）

每次查询时，如果要查询的字符串长度是 k，那我们只需要比对大约 k 个节点，就能完成查询操作。跟原本那组字符串的长度和个数没有任何关系。所以说，构建好 Trie 树后，在其中查找字符串的时间复杂度是 O(k)，k 表示要查找的字符串的长度。

空间复杂度：如果字符串中不仅包含小写字母，还包含大写字母、数字、甚至是中文，那需要的存储空间就更多了。所以，也就是说，在某些情况下，Trie 树不一定会节省存储空间。在重复的前缀并不多的情况下，Trie 树不但不能节省内存，还有可能会浪费更多的内存。

Trie树的应用场景

1. 字符串中包含的字符集不能太大，如果字符集过大，存储空间就会浪费很多
2. 要求字符串的前缀重合比较多，不然空间消耗会变大很多。
3. 需要自己实现 Trie 树，在工程上是将简单问题复杂化
4. 通过指针串起来的数据块是不连续的，而 Trie 树中用到了指针，所以，对缓存并不友好，性能上会打个折扣。

Trie 树比较适合的是查找前缀匹配的字符串