【LeetCode】208.实现Trie（前缀树）（java+c++，两种方法实现，详细图解）
题目
分析

分析

解题思路

这是一种叫做 单词查找树 的结构。它由字符串键中所有的字符构造而成，允许使用被查找键中的字符进行查找。其中包括插入、查找、删除，寻找前缀等操作。接下来先介绍Trie树的基本性质。

先看下面的例子：

【LeetCode】208.实现Trie（前缀树）（java+c++，两种方法实现，详细图解）
题目
分析

现在有5个word，分别为by,by,hello,heat,the。所构成的TrieTree如图所示，其中包含一个根节点，值为空，跟几点所连接的是每个word的第一个字符，每个字符按照同样的方式生成与之连接的字符的TrieTree，在每个word的最末处，表示该word出现了几次。例如：“b”处为0，表示"b"这个单词没有出现过。“y”处为2，表示“by”这个单词出现了两次。

单词查找树之所以有这样的，是由于我们对于其结点的特殊定义。单词查找树的每一个节点都包含了下一个可能出现的字符的链接。从根节点开始，首先经过的是word的首字母所对应的链接，在下一个节点中沿着第二个字符所对应的链接继续前进，在第二个节点中沿着第三个字符所对应的链接向前，这样到达最后一个字符所指向的节点就结束。接下来我们来看对其节点的定义。

1. TrieNode

定义单词查找树的结点为：

public class TrieNode{
    public int path;
    public int end;
    public HashMap<Character, TrieNode> next;

    public TrieNode(){
        path = 0;
        end = 0;
        next = new HashMap<>();
    }
}

path：表示当前节点所能链接到其他节点的个数（在删除操作中会用到）
end：表示以当前节点为结尾的单词的个数
next：HashMap<Character, TrieNode>类型，表示当前节点能链接到的所有节点。

这里next同样可以使用字符数组来表示，例如字符的范围是小写字母，可以以'a'~'z'字符作为索引，这样相比起哈希表来会提高查找速度，但每一个点都含有一个值和26个链接，这样会多出好多空节点，如图所示：

【LeetCode】208.实现Trie（前缀树）（java+c++，两种方法实现，详细图解）
题目
分析
该图片来自网络

2.insert操作

如同链表的生成过程一样，从根节点开始，如果根节点所连接的节点中没有当前字符，则生成一个值为当前字符的新节点，插入其中；如果有当前字符，则则继续进行匹配，并在过程中对每一个匹配到的节点path进行计数，重复上述过程，直到插完最后一个字符，并在最后一个字符的节点end进行计数，表示已经该单词的插入操作已经完成。

public void insert(String word){
    if(word == null || word.equals(""))  return ;
    TrieNode node = root;
    for(int i = 0; i<word.length(); i++){
        char ch = word.charAt(i);
        if(!node.next.containsKey(ch)) {
            node.next.put(ch,new TrieNode());
        }
        node = node.next.get(ch);
        node.path++;
    }
    node.end++;
}

2.search操作

同insert操作基本相同，由于我这里使用的是Hashmap进行的节点存储，故如果在匹配的过程中没能匹配到，则表示搜索失败，匹配到后最后一个字符时，如果当前end值不为零，则表示匹配成功。

public boolean search(String word){
    if(word == null || word.equals("")) return false;
    TrieNode node = root;
    for(int i = 0; i<word.length(); i++){
        char ch = word.charAt(i);
        if(!node.next.containsKey(ch)) return false;
        node = node.next.get(ch);
    }
    if(node.end == 0) return false;
    return true;
}

3.startwith操作

同search操作基本相同，只是这里判断到最后一个字符的时候，不需要判断end值。因为这里只需要检查前缀是否存在。

public boolean startsWith(String word){
    if(word == null || word.equals("")) return false;
    TrieNode node = root;
    for(int i = 0; i<word.length(); i++){
        char ch = word.charAt(i);
        if(!node.next.containsKey(ch)) return false;
        node = node.next.get(ch);
    }
    return true;
}

4.delete操作

delete操作同上述操作大致相同，这里需要使用到path变量，回忆一下，path：表示当前节点所能链接到其他节点的个数。还以五个单词为例，例如删除’the’，当匹配到‘t’时，由于进行path–操作后，此时判断path为0，过可直接将当前节点置空，后面的数据则不用再去遍历即可。java中的垃圾回收机制会处理其他的被断开的节点，如果在C++中，则需要全部匹配，之后调用析构函数去操作。

public void delete(String word){
    if(word == null || word.equals("") || !search(word)) return ;
    TrieNode node = root;
    for (int i = 0; i < word.length(); i++) {
        char ch = word.charAt(i);
        if(--node.next.get(ch).path == 0){
            node.next.remove(ch);
            return;
        }
        node = node.next.get(ch);
    }
    node.end--;
}

刚才的列出了insert、search、startwith、delete四种操作，由于本题没有要求delete操作，故在最终代码中不体现,但delete操作还是要掌握的。

代码

java实现 map

public class Trie {
    public class TrieNode{
    public int path;
    public int end;
    public HashMap<Character, TrieNode> next;

    public TrieNode(){
        path = 0;
        end = 0;
        next = new HashMap<>();
    }
}

    private TrieNode root;
    public Trie(){
        root = new TrieNode();
    }

    public void insert(String word){
        if(word == null || word.equals(""))  return ;
        TrieNode node = root;
        for(int i = 0; i<word.length(); i++){
            char ch = word.charAt(i);
            if(!node.next.containsKey(ch)) {
                node.next.put(ch,new TrieNode());
            }
            node = node.next.get(ch);
            node.path++;
        }
        node.end++;
    }

    public boolean search(String word){
        if(word == null || word.equals("")) return false;
        TrieNode node = root;
        for(int i = 0; i<word.length(); i++){
            char ch = word.charAt(i);
            if(!node.next.containsKey(ch)) return false;
            node = node.next.get(ch);
        }
        if(node.end == 0) return false;
        return true;
    }
    public boolean startsWith(String word){
        if(word == null || word.equals("")) return false;
        TrieNode node = root;
        for(int i = 0; i<word.length(); i++){
            char ch = word.charAt(i);
            if(!node.next.containsKey(ch)) return false;
            node = node.next.get(ch);
        }
        return true;
    }
}

/**
 * Your Trie object will be instantiated and called as such:
 * Trie obj = new Trie();
 * obj.insert(word);
 * boolean param_2 = obj.search(word);
 * boolean param_3 = obj.startsWith(prefix);
 */

C++实现，仅供参考。

class Trie {
public:
    class TrieNode {
    public:
        int path;   // 当前节点所能链接到其他节点的个数，该成员可以没有
        int end;    // 以当前节点为结尾的单词的个数
        unordered_map<char, TrieNode*> next;    // 当前节点能链接到的所有节点
        
        TrieNode () {
            path = 0;
            end = 0;
            next = unordered_map<char, TrieNode*> {};
        }
    };

    TrieNode *root;
    Trie() {
        root = new TrieNode();
    }
    
    void insert(string word) {
        if (word.empty())
            return ;
        TrieNode *node = root;
        for (int i = 0; i < word.length(); i++) {
            char ch = word[i];
            if (node->next.count(ch) == 0) {
                node->next[ch] = new TrieNode();
            }
            node = node->next[ch];
            node->path++;
        }
        node->end++;
    }
    
    bool search(string word) {
        if (word.empty())
            return false;
        TrieNode *node = root;
        for (int i = 0; i < word.length(); i++) {
            char ch = word[i];
            if (node->next.count(ch) == 0)
                return false;
            node = node->next[ch];
        }
        if (node->end == 0) // 若不成立，说明此时word仅是这条分支上的prefix，因此在startWith方法中，把这个判断去掉即可
            return false;
        return true;
    }
    
    bool startsWith(string prefix) {
        if (prefix.empty()) 
            return false;
        TrieNode *node = root;
        for (int i = 0; i < prefix.length(); i++) {
            char ch = prefix[i];
            if (node->next.count(ch) == 0) 
                return false;
            node = node->next[ch];
        }
        return true;
    }
};

java索引实现

class Trie {
    private final int ALPHABET_SIZE = 26;
    private Trie[] children = new Trie[ALPHABET_SIZE];
    boolean isEndOfWord = false;
    public Trie() {}
    
    public void insert(String word) {
        Trie tmp = this;
        for (char i : word.toCharArray()) {
            if (tmp.children[i-'a'] == null) {
                tmp.children[i-'a'] = new Trie();
            }
            tmp = tmp.children[i-'a'];
        }
        tmp.isEndOfWord = true;
    }
    
    public boolean search(String word) {
        Trie tmp = this;
        for (char i : word.toCharArray()) {
            if (tmp.children[i-'a'] == null) {
                return false;
            }
            tmp = tmp.children[i-'a'];
        }
        return tmp.isEndOfWord ? true : false;
    }
    
    public boolean startsWith(String prefix) {
        Trie tmp = this;
        for (char i : prefix.toCharArray()) {
            if (tmp.children[i-'a'] == null) {
                return false;
            }
            tmp = tmp.children[i-'a'];
        }
        return true;
    }
}

【LeetCode】208.实现Trie（前缀树）（java+c++，两种方法实现，详细图解） 题目 分析

分析