You signed in with another tab or window. Reload to refresh your session.You signed out in another tab or window. Reload to refresh your session.You switched accounts on another tab or window. Reload to refresh your session.Dismiss alert
class Trie {
TreeNode root;
class TreeNode {
TreeNode[] nodes = new TreeNode[26];
boolean end = false;
}
/** Initialize your data structure here. */
public Trie() {
root = new TreeNode();
}
/** Inserts a word into the trie. */
public void insert(String word) {
TreeNode tmp = root;
for (int i = 0; i < word.length(); ++i) {
int idx = word.charAt(i) - 'a';
if (tmp.nodes[idx] == null) {
tmp.nodes[idx] = new TreeNode();
}
tmp = tmp.nodes[idx];
}
tmp.end = true;
}
private TreeNode searchNode(String word) {
TreeNode tmp = root;
for (int i = 0; i < word.length(); ++i) {
int idx = word.charAt(i) - 'a';
if (tmp.nodes[idx] == null) {
return null;
}
tmp = tmp.nodes[idx];
}
return tmp;
}
/** Returns if the word is in the trie. */
public boolean search(String word) {
TreeNode tmp = searchNode(word);
return tmp == null ? false : tmp.end;
}
/** Returns if there is any word in the trie that starts with the given prefix. */
public boolean startsWith(String prefix) {
return searchNode(prefix) == null ? false : true;
}
}
/**
* Your Trie object will be instantiated and called as such:
* Trie obj = new Trie();
* obj.insert(word);
* boolean param_2 = obj.search(word);
* boolean param_3 = obj.startsWith(prefix);
*/
Implement a trie with
insert
,search
, andstartsWith
methods.Example:
Note:
a-z
.这道题是字典树(Trie) 的入门题目,又称前缀树(prefix tree)或者单词查找树。字典树是一个用来检索字符串(验证一个字符串是否在一堆字符串中或者是前缀)、字符串最长公共前缀等功能的数据结构。
Trie是一个用空间换取时间的应用,插入、查找的时间复杂度均为O(N),其中N为字符串长度,而 空间复杂度是26^n级别的,非常庞大(可采用双数组实现改善)。
详细资料可以观看参考资料。LeetCode中还有关于字典树的类似题目还有No.211题,其中难点在于如何解决正则表达式中的“.”表达,使用了典型的DFS方法,参数表示下标而不再是字符串
我没有想出来,太蠢了。具体如何实现看如下代码:
类似题目:
参考资料:
The text was updated successfully, but these errors were encountered: