Description#
A trie (pronounced as "try") or prefix tree is a tree data structure used to efficiently store and retrieve keys in a dataset of strings. There are various applications of this data structure, such as autocomplete and spellchecker.
Implement the Trie class:
Trie() Initializes the trie object.void insert(String word) Inserts the string word into the trie.boolean search(String word) Returns true if the string word is in the trie (i.e., was inserted before), and false otherwise.boolean startsWith(String prefix) Returns true if there is a previously inserted string word that has the prefix prefix, and false otherwise.
Example 1:
Input
["Trie", "insert", "search", "search", "startsWith", "insert", "search"]
[[], ["apple"], ["apple"], ["app"], ["app"], ["app"], ["app"]]
Output
[null, null, true, false, true, null, true]
Explanation
Trie trie = new Trie();
trie.insert("apple");
trie.search("apple"); // return True
trie.search("app"); // return False
trie.startsWith("app"); // return True
trie.insert("app");
trie.search("app"); // return True
Constraints:
1 <= word.length, prefix.length <= 2000word and prefix consist only of lowercase English letters.- At most
3 * 104 calls in total will be made to insert, search, and startsWith.
Solutions#
Solution 1#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
| class Trie:
def __init__(self):
self.children = [None] * 26
self.is_end = False
def insert(self, word: str) -> None:
node = self
for c in word:
idx = ord(c) - ord('a')
if node.children[idx] is None:
node.children[idx] = Trie()
node = node.children[idx]
node.is_end = True
def search(self, word: str) -> bool:
node = self._search_prefix(word)
return node is not None and node.is_end
def startsWith(self, prefix: str) -> bool:
node = self._search_prefix(prefix)
return node is not None
def _search_prefix(self, prefix: str):
node = self
for c in prefix:
idx = ord(c) - ord('a')
if node.children[idx] is None:
return None
node = node.children[idx]
return node
# Your Trie object will be instantiated and called as such:
# obj = Trie()
# obj.insert(word)
# param_2 = obj.search(word)
# param_3 = obj.startsWith(prefix)
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
| class Trie {
private Trie[] children;
private boolean isEnd;
public Trie() {
children = new Trie[26];
}
public void insert(String word) {
Trie node = this;
for (char c : word.toCharArray()) {
int idx = c - 'a';
if (node.children[idx] == null) {
node.children[idx] = new Trie();
}
node = node.children[idx];
}
node.isEnd = true;
}
public boolean search(String word) {
Trie node = searchPrefix(word);
return node != null && node.isEnd;
}
public boolean startsWith(String prefix) {
Trie node = searchPrefix(prefix);
return node != null;
}
private Trie searchPrefix(String s) {
Trie node = this;
for (char c : s.toCharArray()) {
int idx = c - 'a';
if (node.children[idx] == null) {
return null;
}
node = node.children[idx];
}
return node;
}
}
/**
* 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);
*/
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
| class Trie {
private:
vector<Trie*> children;
bool isEnd;
Trie* searchPrefix(string s) {
Trie* node = this;
for (char c : s) {
int idx = c - 'a';
if (!node->children[idx]) return nullptr;
node = node->children[idx];
}
return node;
}
public:
Trie()
: children(26)
, isEnd(false) {}
void insert(string word) {
Trie* node = this;
for (char c : word) {
int idx = c - 'a';
if (!node->children[idx]) node->children[idx] = new Trie();
node = node->children[idx];
}
node->isEnd = true;
}
bool search(string word) {
Trie* node = searchPrefix(word);
return node != nullptr && node->isEnd;
}
bool startsWith(string prefix) {
Trie* node = searchPrefix(prefix);
return node != nullptr;
}
};
/**
* Your Trie object will be instantiated and called as such:
* Trie* obj = new Trie();
* obj->insert(word);
* bool param_2 = obj->search(word);
* bool param_3 = obj->startsWith(prefix);
*/
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
| type Trie struct {
children [26]*Trie
isEnd bool
}
func Constructor() Trie {
return Trie{}
}
func (this *Trie) Insert(word string) {
node := this
for _, c := range word {
idx := c - 'a'
if node.children[idx] == nil {
node.children[idx] = &Trie{}
}
node = node.children[idx]
}
node.isEnd = true
}
func (this *Trie) Search(word string) bool {
node := this.SearchPrefix(word)
return node != nil && node.isEnd
}
func (this *Trie) StartsWith(prefix string) bool {
node := this.SearchPrefix(prefix)
return node != nil
}
func (this *Trie) SearchPrefix(s string) *Trie {
node := this
for _, c := range s {
idx := c - 'a'
if node.children[idx] == nil {
return nil
}
node = node.children[idx]
}
return node
}
/**
* Your Trie object will be instantiated and called as such:
* obj := Constructor();
* obj.Insert(word);
* param_2 := obj.Search(word);
* param_3 := obj.StartsWith(prefix);
*/
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
| class TrieNode {
children;
isEnd;
constructor() {
this.children = new Array(26);
this.isEnd = false;
}
}
class Trie {
root;
constructor() {
this.root = new TrieNode();
}
insert(word: string): void {
let head = this.root;
for (let char of word) {
let index = char.charCodeAt(0) - 97;
if (!head.children[index]) {
head.children[index] = new TrieNode();
}
head = head.children[index];
}
head.isEnd = true;
}
search(word: string): boolean {
let head = this.searchPrefix(word);
return head != null && head.isEnd;
}
startsWith(prefix: string): boolean {
return this.searchPrefix(prefix) != null;
}
private searchPrefix(prefix: string) {
let head = this.root;
for (let char of prefix) {
let index = char.charCodeAt(0) - 97;
if (!head.children[index]) return null;
head = head.children[index];
}
return head;
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
| use std::{ rc::Rc, cell::RefCell, collections::HashMap };
struct TrieNode {
pub val: Option<char>,
pub flag: bool,
pub child: HashMap<char, Rc<RefCell<TrieNode>>>,
}
impl TrieNode {
fn new() -> Self {
Self {
val: None,
flag: false,
child: HashMap::new(),
}
}
fn new_with_val(val: char) -> Self {
Self {
val: Some(val),
flag: false,
child: HashMap::new(),
}
}
}
struct Trie {
root: Rc<RefCell<TrieNode>>,
}
/// Your Trie object will be instantiated and called as such:
/// let obj = Trie::new();
/// obj.insert(word);
/// let ret_2: bool = obj.search(word);
/// let ret_3: bool = obj.starts_with(prefix);
impl Trie {
fn new() -> Self {
Self {
root: Rc::new(RefCell::new(TrieNode::new())),
}
}
fn insert(&self, word: String) {
let char_vec: Vec<char> = word.chars().collect();
// Get the clone of current root node
let mut root = Rc::clone(&self.root);
for c in &char_vec {
if !root.borrow().child.contains_key(c) {
// We need to manually create the entry
root.borrow_mut().child.insert(*c, Rc::new(RefCell::new(TrieNode::new())));
}
// Get the child node
let root_clone = Rc::clone(root.borrow().child.get(c).unwrap());
root = root_clone;
}
{
root.borrow_mut().flag = true;
}
}
fn search(&self, word: String) -> bool {
let char_vec: Vec<char> = word.chars().collect();
// Get the clone of current root node
let mut root = Rc::clone(&self.root);
for c in &char_vec {
if !root.borrow().child.contains_key(c) {
return false;
}
// Get the child node
let root_clone = Rc::clone(root.borrow().child.get(c).unwrap());
root = root_clone;
}
let flag = root.borrow().flag;
flag
}
fn starts_with(&self, prefix: String) -> bool {
let char_vec: Vec<char> = prefix.chars().collect();
// Get the clone of current root node
let mut root = Rc::clone(&self.root);
for c in &char_vec {
if !root.borrow().child.contains_key(c) {
return false;
}
// Get the child node
let root_clone = Rc::clone(root.borrow().child.get(c).unwrap());
root = root_clone;
}
true
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
| /**
* Initialize your data structure here.
*/
var Trie = function () {
this.children = {};
};
/**
* Inserts a word into the trie.
* @param {string} word
* @return {void}
*/
Trie.prototype.insert = function (word) {
let node = this.children;
for (let char of word) {
if (!node[char]) {
node[char] = {};
}
node = node[char];
}
node.isEnd = true;
};
/**
* Returns if the word is in the trie.
* @param {string} word
* @return {boolean}
*/
Trie.prototype.search = function (word) {
let node = this.searchPrefix(word);
return node != undefined && node.isEnd != undefined;
};
Trie.prototype.searchPrefix = function (prefix) {
let node = this.children;
for (let char of prefix) {
if (!node[char]) return false;
node = node[char];
}
return node;
};
/**
* Returns if there is any word in the trie that starts with the given prefix.
* @param {string} prefix
* @return {boolean}
*/
Trie.prototype.startsWith = function (prefix) {
return this.searchPrefix(prefix);
};
/**
* Your Trie object will be instantiated and called as such:
* var obj = new Trie()
* obj.insert(word)
* var param_2 = obj.search(word)
* var param_3 = obj.startsWith(prefix)
*/
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
| public class Trie {
bool isEnd;
Trie[] children = new Trie[26];
public Trie() {
}
public void Insert(string word) {
Trie node = this;
foreach (var c in word)
{
var idx = c - 'a';
node.children[idx] ??= new Trie();
node = node.children[idx];
}
node.isEnd = true;
}
public bool Search(string word) {
Trie node = SearchPrefix(word);
return node != null && node.isEnd;
}
public bool StartsWith(string prefix) {
Trie node = SearchPrefix(prefix);
return node != null;
}
private Trie SearchPrefix(string s) {
Trie node = this;
foreach (var c in s)
{
var idx = c - 'a';
if (node.children[idx] == null)
{
return null;
}
node = node.children[idx];
}
return node;
}
}
/**
* Your Trie object will be instantiated and called as such:
* Trie obj = new Trie();
* obj.Insert(word);
* bool param_2 = obj.Search(word);
* bool param_3 = obj.StartsWith(prefix);
*/
|
