字典树（前缀树）

字典树（前缀树）

概述：

字典树（Trie）用于判断字符串是否存在或者是否具有某种字符串前缀。

为什么需要用字典树解决这类问题呢？假如我们有一个储存了近万个单词的字典，即使我们使用哈希，在其中搜索一个单词的实际开销也是非常大的，且无法轻易支持搜索单词前缀。然而由于一个英文单词的长度 n 通常在 10 以内，如果我们使用字典树，则可以在 O(n)——近似 O(1)的时间内完成搜索，且额外开销非常小。

Trie（字典树），又称前缀树，是一棵有根树，其每个节点包含以下字段：

• 指向子节点的指针数组 children。数组长度为 26，即小写英文字母的数量。此时children[0] 对应小写字母 a，children[1] 对应小写字母 b，…，children[25] 对应小写字母 z。
• 布尔字段 isEnd，表示该节点是否为字符串的结尾。

插入字符串

我们从字典树的根开始，插入字符串。对于当前字符对应的子节点，有两种情况：

• 子节点存在。沿着指针移动到子节点，继续处理下一个字符。
• 子节点不存在。创建一个新的子节点，记录在 children 数组的对应位置上，然后沿着指针移动到子节点，继续搜索下一个字符。

重复以上步骤，直到处理字符串的最后一个字符，然后将当前节点标记为字符串的结尾。

查找前缀

我们从字典树的根开始，查找前缀。对于当前字符对应的子节点，有两种情况：

• 子节点存在。沿着指针移动到子节点，继续搜索下一个字符。
• 子节点不存在。说明字典树中不包含该前缀，返回空指针。

重复以上步骤，直到返回空指针或搜索完前缀的最后一个字符。

若搜索到了前缀的末尾，就说明字典树中存在该前缀。此外，若前缀末尾对应节点的 isEnd 为真，则说明字典树中存在该字符串。

java代码实现：

class Trie {
    TrieNode root;

    public Trie() {
        this.root = new TrieNode();
    }

    // 向字典树插入一个词
    void insert(String word) {
        TrieNode temp = root;
        for (int i = 0; i < word.length(); ++i) {
            if (temp.childNode[word.charAt(i) - 'a'] == null) {
                temp.childNode[word.charAt(i) - 'a'] = new TrieNode();
            }
            temp = temp.childNode[word.charAt(i) - 'a'];
        }
        temp.isVal = true;
    }

    // 判断字典树里是否有一个词
    boolean search(String word) {
        TrieNode temp = root;
        for (int i = 0; i < word.length(); ++i) {
            if (temp == null) {
                break;
            }
            temp = temp.childNode[word.charAt(i) - 'a'];
        }
        return temp != null ? temp.isVal : false;
    }

    // 判断字典树是否有一个以词开始的前缀
    boolean startsWith(String prefix) {
        TrieNode temp = root;
        for (int i = 0; i < prefix.length(); ++i) {
            if (temp == null) {
                break;
            }
            temp = temp.childNode[prefix.charAt(i) - 'a'];
        }
        return temp != null;
    }
}

class TrieNode {
    public TrieNode[] childNode;
    boolean isVal;

    public TrieNode() {
        childNode = new TrieNode[26];
        isVal = false;
        for (int i = 0; i < 26; ++i) {
            childNode[i] = null;
        }
    }
}

C++代码实现：

class TrieNode {
public:
    TrieNode* childNode[26];
    bool isVal;
    TrieNode(): isVal(false) {
        for (int i = 0; i < 26; ++i) {
            childNode[i] = nullptr;
        }
    }
};
class Trie {
    TrieNode* root;
public:
    Trie(): root(new TrieNode()) {}

    // 向字典树插入一个词
    void insert(string word) {
        TrieNode* temp = root;
        for (int i = 0; i < word.size(); ++i) {
            if (!temp->childNode[word[i]-’a’]) {
                temp->childNode[word[i]-’a’] = new TrieNode();
            }
            temp = temp->childNode[word[i]-’a’];
        }
        temp->isVal = true;
    }
    
    // 判断字典树里是否有一个词
    bool search(string word) {
    TrieNode* temp = root;
        for (int i = 0; i < word.size(); ++i) {
            if (!temp) {
                break;
            }
            temp = temp->childNode[word[i]-’a’];
        }
        return temp? temp->isVal: false;
    }
    
    // 判断字典树是否有一个以词开始的前缀
    bool startsWith(string prefix) {
        TrieNode* temp = root;
        for (int i = 0; i < prefix.size(); ++i) {
            if (!temp) {
                break;
            }
            temp = temp->childNode[prefix[i]-’a’];
        }
        return temp;
    }
};

练习：
208. Implement Trie (Prefix Tree)