LEETCODE 208. Implement Trie (Prefix Tree) 解题思路分析

题目大意:

实现 Trie (前缀树)

实现一个 Trie (前缀树),包含 insertsearch, 和 startsWith 这三个操作。

示例:

Trie trie = new Trie();

trie.insert("apple");
trie.search("apple"); // 返回 true
trie.search("app"); // 返回 false
trie.startsWith("app"); // 返回 true
trie.insert("app");
trie.search("app"); // 返回 true

说明:

  • 你可以假设所有的输入都是由小写字母 a-z 构成的。
  • 保证所有输入均为非空字符串。

如果想查看本题目是哪家公司的面试题,请参考以下免费链接: https://leetcode.jp/problemdetail.php?id=208

解题思路分析:

Trie被称为前缀树,也叫做字典树,它是一个经典的树形结构。既然是树形结构,那么就少不了节点,对于字典树的节点我们可以定义为:

class Node{
    // 是否存在以当前节点结尾的单词
    boolean isWord;
    // 当前节点的后续字符
    Node[] children = new Node[26];
}

我们在之前的文章中非常详细的介绍过有关字典树Trie的的数据存储结构:LEETCODE 1268. Search Suggestions System 解题思路分析,这里就不再重复了。本题可以说是字典树最为简单的一个应用场景,如果你是第一次接触到这个概念或者你对字典树还不够了解,强烈建议你先去学习一下上面这篇文章。

实现代码:

class Node{
    boolean isWord;
    Node[] children = new Node[26];
}
    
Node root = new Node();
/** Initialize your data structure here. */
public Trie() {

}

/** Inserts a word into the trie. */
public void insert(String word) {
    Node node = root;
    char[] arr = word.toCharArray();
    for(char c : arr){
        Node[] children = node.children;
        if(children[c-'a']==null) children[c-'a'] = new Node();
        node=children[c-'a'];
    }
    node.isWord=true;
}

/** Returns if the word is in the trie. */
public boolean search(String word) {
    Node node = root;
    char[] arr = word.toCharArray();
    for(char c : arr){
        Node[] children = node.children;
        if(children[c-'a']==null) return false;
        node=children[c-'a'];
    }
    return node.isWord;
}

/** Returns if there is any word in the trie that starts with the given prefix. */
public boolean startsWith(String prefix) {
    Node node = root;
    char[] arr = prefix.toCharArray();
    for(char c : arr){
        Node[] children = node.children;
        if(children[c-'a']==null) return false;
        node=children[c-'a'];
    }
    return true;
}

本题解法执行时间为29ms。

Runtime: 29 ms, faster than 98.16% of Java online submissions for Implement Trie (Prefix Tree).

Memory Usage: 50.3 MB, less than 100.00% of Java online submissions for Implement Trie (Prefix Tree).

本网站文章均为原创内容,并可随意转载,但请标明本文链接
如有任何疑问可在文章底部留言。为了防止恶意评论,本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言,并会在第一时间对您的留言进行回复!欢迎交流!
本文链接: http://leetcode.jp/leetcode-208-implement-trie-prefix-tree-解题思路分析/
此条目发表在leetcode分类目录,贴了, , 标签。将固定链接加入收藏夹。

发表评论

您的电子邮箱地址不会被公开。