欢迎访问LeetCode题解合集

题目描述

实现一个 Trie (前缀树)，包含 insert, search, 和 startsWith 这三个操作。

示例:

Trie trie = new Trie();

trie.insert("apple");
trie.search("apple");   // 返回 true
trie.search("app");     // 返回 false
trie.startsWith("app"); // 返回 true
trie.insert("app");   
trie.search("app");     // 返回 true

说明:

• 你可以假设所有的输入都是由小写字母 a-z 构成的。
• 保证所有输入均为非空字符串。

题解：

每个节点有 a~z 共 26 个子节点，并且需要使用一个标志记录该节点是否是单词的结尾。

插入时遍历 word 中的每个字符，从根节点开始查找，不存在则创建新的节点。

查找和插入过程相似。

时间复杂度：$O(26 * n)$

额外空间复杂度：$O(26 * n)$

n 指非空节点个数

class Trie {
    Trie *son[26] {nullptr};
    bool is_tail = false;
public:
    /** Initialize your data structure here. */
    Trie() {}

    /** Inserts a word into the trie. */
    void insert(string word) {
        Trie *root = this;
        for ( const auto& ch : word ) {
            if ( !root->son[ch - 'a'] )
                root->son[ch - 'a'] = new Trie();
            root = root->son[ch - 'a'];
        }
        root->is_tail = true;
    }

    /** Returns if the word is in the trie. */
    bool search(string word) {
        Trie *root = this;
        for( const auto& ch : word ) {
            if( !root->son[ch - 'a'] )
                return false;
            root = root->son[ch - 'a'];
        }
        return root->is_tail;
    }

    /** Returns if there is any word in the trie that starts with the given prefix. */
    bool startsWith(string prefix) {
        Trie *root = this;
        for( const auto& ch : prefix ) {
            if ( !root->son[ch - 'a'] )
                return false;
            root = root->son[ch - 'a'];
        }
        return true;
    }
};
/*
时间：56ms，击败：96.03%
内存：44MB，击败：27.93%
*/

也可以使用数组来完成：

class Trie {
private:
    const static int N = 31000;
    int son[N][26] {0};
    int idx = 0;
    bool is_tail[N] {false};
public:
    /** Initialize your data structure here. */
    Trie() {}

    /** Inserts a word into the trie. */
    void insert(string word) {
        int p = 0, u;
        for ( auto& ch : word ) {
            u = ch - 'a';
            if( !son[p][u] )
                son[p][u] = ++idx;
            p = son[p][u];
        }
        is_tail[p] = true;
    }

    /** Returns if the word is in the trie. */
    bool search(string word) {
        int p = 0, u;
        for( auto& ch : word ) {
            u = ch - 'a';
            if ( !son[p][u] )
                return false;
            p = son[p][u];
        }
        return is_tail[p];
    }

    /** Returns if there is any word in the trie that starts with the given prefix. */
    bool startsWith(string prefix) {
        int p = 0, u;
        for( auto& ch : prefix ) {
            u = ch - 'a';
            if ( !son[p][u] )
                return false;
            p = son[p][u];
        }
        return true;
    }
};
/*
时间：52ms，击败：98.11%
内存：74.9MB，击败：5.93%
*/