54、图论-实现Trie前缀树-Toy模板网

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

54、图论-实现Trie前缀树,leetcode 热题100,图论,c#,开发语言,java,leetcode,算法

思路：

主要是构建一个trie前缀树结构。如果构建呢？看题意，应该当前节点对象下有几个属性：

1、next节点数组

2、是否为结尾

3、当前值

代码如下：文章来源地址https://www.toymoban.com/news/detail-859239.html

class Trie {

    class Node {
        boolean end;
        Node[] nexts;

        public Node() {
            end = false;
            nexts = new Node[26];
        }
    }

    public Node root;

    public Trie() {
        root = new Node();
    }

    public void insert(String word) {
        if (word == null) {
            return;
        }
        char[] chs = word.toCharArray();
        Node node = root;
        int path;
        for (int i = 0; i < chs.length; i++) {
            path = chs[i] - 'a';
            if (node.nexts[path] == null) {
                node.nexts[path] = new Node();
            }
            node = node.nexts[path];
        }
        node.end = true;
    }

    public boolean search(String word) {
        if (word == null) {
            return false;
        }
        char[] chs = word.toCharArray();
        Node node = root;
        int path;
        for (int i = 0; i < chs.length; i++) {
            path = chs[i] - 'a';
            if (node.nexts[path] == null) {
                return false;
            }
            node = node.nexts[path];
        }
        return node.end;
    }

    public boolean startsWith(String prefix) {
        if (prefix == null) {
            return false;
        }
        char[] chs = prefix.toCharArray();
        int path;
        Node node = root;
        for (int i = 0; i < chs.length; i++) {
            path = chs[i] - 'a';
            if (node.nexts[path] == null) {
                return false;
            }
            node = node.nexts[path];
        }
        return true;
    }
}

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