力扣208题:实现Tire(前缀树)

发布时间:2024年01月21日

【题目链接】

力扣(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);
    }

【解题步骤】

  1. 设计一个前缀节点类,这个类保存了,当前字符所在层级,是否为某个词的词尾,以及后续所有字符的节点,采用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变量的设计:因为词的匹配不光要字符相同,位置也要一样;

    1. 2?是否为某个词的词尾:这个变量也很重要,词尾不一定是叶子节点,因为一个词可能是另一个词的一部分
    • 3?后续所有字符对应的节点变量:采用HashMap存储,肯定是考虑性能因素,查询时间复杂度为O(1)
    1. 4 大家可以看到,这个节点类本身没有存有字符变量,而是放在上一个节点的指向本节点的key中,从减少了重复而不必要的存储;
  2. 设计一个通用的匹配节点查找函数,返回与某个字符串的匹配最深节点:这个匹配函数非常重要,因为无论是插入词,判断字符串?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
    }
  3. 实现Trie()?初始化前缀树对象:因为所有词没有统一的根字符,创建一个虚拟的空的根节点
    // 初始化一个根节点
    root = new TireNode(-1, false);

  4. 编写函数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), i == word.length() - 1);
        }
        // 这个一定要加上,因为插入词的所有字符可能都存在树里,但是作为另外某些词的一部分。
        node.end = true;
    }
  5. 编写函数boolean search(String word)?:首先在前缀树中查找与word最深匹配的节点,最后判断匹配的节点层级是否为词尾,并且此节点为词尾节点。
    public boolean search(String word) {
        TireNode node = match(word);
        // 判断匹配的节点层级是否为词尾,并且此节点为词尾节点。
        return node.level == word.length() - 1 && node.end == true;
    }
  6. 编写函数boolean startsWith(String prefix)??:首先在前缀树中查找与word最深匹配的节点,判断匹配的节点层级是否输入字符串的末尾
    public boolean startsWith(String prefix) {
        TireNode node = match(prefix);
        // 判断匹配的节点层级是否为输入字符串的末尾
        return node.level == prefix.length() - 1;
    }

【思路总结】

  1. 所有树的算法题中,节点类的设计,是必不可少且非常重要,节点中的变量要点到关键并且尽量精简;
  2. 这种算法题目,属于复合应用题,需要借助已有的一些数据结构,比如这里就用到了HashMap;
  3. 前缀树对外提供的功能函数,要根据代码执行逻辑,找到其共性点,设计好内部通用函数,一旦内部通用函数设计好,公共的功能函数只需要在此基础上进行封装即可,达到最大的代码复用,并通过这种“正交性”分解,降解了程序的复杂性
文章来源:https://blog.csdn.net/IT_Fly/article/details/135726099
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。