实现Trie Tree(实现前缀树)(LeetCode.208

题目

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

LeetCode.208

解析与编码实现

1. 什么是Trie Tree?

前缀树，也称为字典树或查找树，是一种树形结构。典型应用是用于统计，排序和保存大量的字符串，利用字符串的公共前缀来减少查询时间，减少存储空间，并且最大限度地减少无谓的字符串比较。

Trie Tree如图所示——图片来源于网络

2. Trie Tree Node的结构定义

题目中要求，输入都是由小写字母a-z构成的，一个Node初始化26个孩子节点引用（26个小写英文字母），26个孩子节点使用数组结构实现，a-z固定在对应的数组元素上，虽然这样会有存储上的损耗，某些字母并没有存在，但是通过a-z可以直接定位到数组的元素查询时间复杂度O(1)。

• insert操作可以沿着根节点root（不存储任何值）依次向下遍历和插入。
• startsWith操作前缀匹配，从root出发向下遍历，如果对应的字符节点均存在，则返回true，表明找到了。只要一个字符对应的节点不存在就没有找到。
• search操作从root出发，需要全部匹配的同时，还要确定最后一个匹配的字符节点是否是存储的字符串中的某个字符串最后的一个字符，也就是某个字符串的结束位置。例如，树中存储了abcd，那么search(abc)时，匹配的最后一个字符节点是c，而c不是存储的字符串中的某个字符串最后的一个字符，所以不匹配。这样在Node结构中我们需要增加一个标志符用于标记当前节点是否是存储的某个字符串的最后一个字符。

Trie Tree Node的结构代码如下：

class TrieNode {
    private final int R = 26;
    //代表的字符a-z
    private String val;
    //初始化26个子节点
    private TrieNode[] children;
    //标记当前节点是否是存储的某个字符串的最后一个字符
    private boolean isEnd;

    public TrieNode(String val){
        this.val = val;
        this.children = new TrieNode[R];
        this.isEnd = false;
    }

    public String getVal(){
        return val;
    }

    public TrieNode[] getChildren(){
        return children;
    }

    public void setIsEnd(boolean isEnd){
        this.isEnd = isEnd;
    }

    public boolean getIsEnd(){
        return this.isEnd;
    }
}

3. insert操作

沿着根节点root（不存储任何值）依次向下遍历，如果字符存在继续向下，若不存在插入这个字符。当到达字符串的最后一个字符时，将节点的isEnd标记为true，表示到这个字符为止存储了一个字符串。

代码如下：

public void insert(String word) {
    TrieNode parent = root;
    //向下遍历
    for(int i = 0; i < word.length(); i++){
        //a-z对应的节点位置
        int index = (int)(word.charAt(i) - 'a');
        TrieNode child = parent.getChildren()[index];
        //若不存在当前字符的节点，插入
        if (null == child){
            child = new TrieNode(word.substring(i, i + 1));
            parent.getChildren()[index] = child;
        }
        //继续向下
        parent = child;
    }
    //最后一个字符的节点isEnd标记为true
    parent.setIsEnd(true);
}

4. search操作

从root出发，向下遍历寻找，如果字符节点不存在，则返回false。当字符串都遍历完成，并且对应节点都存在时，需要判断最后一个字符节点的isEnd是否为true，若为true则证明搜寻到对应的字符串。

代码如下：

public boolean search(String word) {
    TrieNode parent = root;
    //从root出发，向下遍历寻找
    for(int i = 0; i < word.length(); i++){
        int index = (int)(word.charAt(i) - 'a');
        TrieNode child = parent.getChildren()[index];
        //如果字符节点不存在，则返回false
        if (null == child){
            return false;
        }
        parent = child;
    }
    //判断最后一个字符节点的isEnd如果是false，表明不是字符串最后一个字符
    if (!parent.getIsEnd()){
        return false;
    }
    return true;
}

5. startsWith操作

root出发向下遍历，如果对应的字符节点均存在，则返回true。只要一个字符对应的节点不存在就没有找到。

代码如下：

public boolean startsWith(String prefix) {
    TrieNode parent = root;
    //从root出发，向下遍历寻找
    for(int i = 0; i < prefix.length(); i++){
        int index = (int)(prefix.charAt(i) - 'a');
        TrieNode child = parent.getChildren()[index];
        //只要一个字符对应的节点不存在就没有找到
        if (null == child){
            return false;
        }
        parent = child;
    }
    return true;
}

完整代码如下

class Trie {
    private TrieNode root;
    /** Initialize your data structure here. */
    public Trie() {
        root = new TrieNode(null);
    }
    
    public void insert(String word) {
        TrieNode parent = root;
        //向下遍历
        for(int i = 0; i < word.length(); i++){
            //a-z对应的节点位置
            int index = (int)(word.charAt(i) - 'a');
            TrieNode child = parent.getChildren()[index];
            //若不存在当前字符的节点，插入
            if (null == child){
                child = new TrieNode(word.substring(i, i + 1));
                parent.getChildren()[index] = child;
            }
            //继续向下
            parent = child;
        }
        //最后一个字符的节点isEnd标记为true
        parent.setIsEnd(true);
    }
    
    public boolean search(String word) {
        TrieNode parent = root;
        //从root出发，向下遍历寻找
        for(int i = 0; i < word.length(); i++){
            int index = (int)(word.charAt(i) - 'a');
            TrieNode child = parent.getChildren()[index];
            //如果字符节点不存在，则返回false
            if (null == child){
                return false;
            }
            parent = child;
        }
        //判断最后一个字符节点的isEnd如果是false，表明不是字符串最后一个字符
        if (!parent.getIsEnd()){
            return false;
        }
        return true;
    }
    
    public boolean startsWith(String prefix) {
       TrieNode parent = root;
        //从root出发，向下遍历寻找
        for(int i = 0; i < prefix.length(); i++){
            int index = (int)(prefix.charAt(i) - 'a');
            TrieNode child = parent.getChildren()[index];
            //只要一个字符对应的节点不存在就没有找到
            if (null == child){
                return false;
            }
            parent = child;
        }
        return true;
    }
}
class TrieNode {
    private final int R = 26;
    //代表的字符a-z
    private String val;
    //初始化26个子节点
    private TrieNode[] children;
    //标记当前节点是否是存储的某个字符串的最后一个字符
    private boolean isEnd;

    public TrieNode(String val){
        this.val = val;
        this.children = new TrieNode[R];
        this.isEnd = false;
    }

    public String getVal(){
        return val;
    }

    public TrieNode[] getChildren(){
        return children;
    }

    public void setIsEnd(boolean isEnd){
        this.isEnd = isEnd;
    }

    public boolean getIsEnd(){
        return this.isEnd;
    }
}