力扣208题：实现Tire（前缀树）-Toy模板网

这篇具有很好参考价值的文章主要介绍了力扣208题：实现Tire（前缀树）。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

【题目链接】

力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台

【解题代码】

public class Trie {

    public class TireNode {

        private int level; // 所在层级
        private boolean end; // 是否为词尾
        private HashMap<Character, TireNode> nextChs; // 后续所有词节点

        TireNode(int level, boolean end) {
            this.level = level;
            this.end = end;
        }
        // 插入下一几点
        public TireNode putNext(char ch, boolean end) {
            TireNode newNode = new TireNode(this.level + 1, end);
            if (this.nextChs == null) this.nextChs = new HashMap<>();
            this.nextChs.put(ch, newNode);
            return newNode;
        }

    }
    private TireNode root;

    public Trie() {
        // 初始化一个根节点
        root = new TireNode(-1, false);
    }

    public void insert(String word) {
        TireNode node = match(word);
        for (int i = node.level + 1; i < word.length(); i++) {
            node = node.putNext(word.charAt(i), i == word.length() - 1);
        }
        // 这个一定要加上，因为插入词的所有字符可能都存在树里，但是作为另外某些词的一部分。
        node.end = true;
    }


    public boolean search(String word) {
        TireNode node = match(word);
        // 判断匹配的节点层级是否为词尾，并且此节点为词尾节点。
        return node.level == word.length() - 1 && node.end == true;
    }

    public boolean startsWith(String prefix) {
        TireNode node = match(prefix);
        // 判断匹配的节点层级是否为词尾
        return node.level == prefix.length() - 1;
    }

    // 这是插入和查找等函数的关键基础函数，通过词查找最大匹配的节点
    private TireNode match(String word) {
        TireNode node = root;
        char ch;
        for (int i = 0; i < word.length(); i++) {
            ch = word.charAt(i);
            if (node.nextChs != null && node.nextChs.containsKey(ch)) {
                node = node.nextChs.get(ch);
            } else
                break;
        }
        return node;
    }

    public static void main(String[] args) {
        Trie trie = new Trie();
        trie.insert("apple");
        boolean result = trie.search("apple");   // 返回 True
        System.out.println("result = " + result);
        result = trie.search("app");     // 返回 False
        System.out.println("result = " + result);
        result = trie.startsWith("app"); // 返回 True
        System.out.println("result = " + result);
        trie.insert("app");
        result = trie.search("app");     // 返回 True
        System.out.println("result = " + result);
    }

【解题步骤】

设计一个前缀节点类，这个类保存了，当前字符所在层级，是否为某个词的词尾，以及后续所有字符的节点，采用HashMap存储，key是后续字符，value就是下一个节点对象；
```
public class TireNode {

        private int level; // 所在层级
        private boolean end; // 是否为词尾
        private HashMap<Character, TireNode> nextChs; // 后续所有词节点

        TireNode(int level, boolean end) {
            this.level = level;
            this.end = end;
        }
        // 插入下一几点
        public TireNode putNext(char ch, boolean end) {
            TireNode newNode = new TireNode(this.level + 1, end);
            if (this.nextChs == null) this.nextChs = new HashMap<>();
            this.nextChs.put(ch, newNode);
            return newNode;
        }

    }
```
- 1 字符所在层级level变量的设计：因为词的匹配不光要字符相同，位置也要一样；文章来源地址https://www.toymoban.com/news/detail-811652.html
1. 2 是否为某个词的词尾：这个变量也很重要，词尾不一定是叶子节点，因为一个词可能是另一个词的一部分
- 3 后续所有字符对应的节点变量：采用HashMap存储，肯定是考虑性能因素，查询时间复杂度为O(1)
1. 4 大家可以看到，这个节点类本身没有存有字符变量，而是放在上一个节点的指向本节点的key中，从减少了重复而不必要的存储；

设计一个通用的匹配节点查找函数，返回与某个字符串的匹配最深节点：这个匹配函数非常重要，因为无论是插入词，判断字符串 word 在前缀树，是否存在前缀为某个字符串的词，都可以复用这个函数

// 这是插入和查找等函数的关键基础函数，通过词查找最大匹配的节点
private TireNode match(String word) {
    TireNode node = root;
    char ch;
    for (int i = 0; i < word.length(); i++) {
        ch = word.charAt(i);
        if (node.nextChs != null && node.nextChs.containsKey(ch)) {
            node = node.nextChs.get(ch);
        } else
            break;
    }
   return node
}

实现Trie() 初始化前缀树对象：因为所有词没有统一的根字符，创建一个虚拟的空的根节点
```
// 初始化一个根节点
root = new TireNode(-1, false);
```

编写函数void insert(String word) 向前缀树中插入字符串 word ，首先在前缀树中查找与word最深匹配的节点，然后再将后续字符一一插入树中，最后将词尾字符所在节点的end值设置为true

public void insert(String word) {
    TireNode node = match(word);
    for (int i = node.level + 1; i < word.length(); i++) {
        node = node.putNext(word.charAt(i), false);
    }
    // 这个一定要加上，因为插入词的所有字符可能都存在树里，但是作为另外某些词的一部分。
    node.end = true;
}

编写函数boolean search(String word) ：首先在前缀树中查找与word最深匹配的节点，最后判断匹配的节点层级是否为词尾，并且此节点为词尾节点。

public boolean search(String word) {
    TireNode node = match(word);
    // 判断匹配的节点层级是否为词尾，并且此节点为词尾节点。
    return node.level == word.length() - 1 && node.end == true;
}

编写函数boolean startsWith(String prefix) ：首先在前缀树中查找与word最深匹配的节点，判断匹配的节点层级是否输入字符串的末尾

public boolean startsWith(String prefix) {
    TireNode node = match(prefix);
    // 判断匹配的节点层级是否为输入字符串的末尾
    return node.level == prefix.length() - 1;
}

【思路总结】

所有树的算法题中，节点类的设计，是必不可少且非常重要，节点中的变量要点到关键并且尽量精简；
这种算法题目，属于复合应用题，需要借助已有的一些数据结构，比如这里就用到了HashMap；
前缀树对外提供的功能函数，要根据代码执行逻辑，找到其共性点，设计好内部通用函数，一旦内部通用函数设计好，公共的功能函数只需要在此基础上进行封装即可，达到最大的代码复用，并通过这种“正交性”分解，降解了程序的复杂性

到了这里，关于力扣208题：实现Tire（前缀树）的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！