Implement Trie (Prefix Tree), by Leetcode
Here is the problem: https://leetcode.com/problems/implement-trie-prefix-tree/description/
I've written about Tries before (https://anothercasualcoder.blogspot.com/2018/09/a-simple-trie-for-prefix-match-problem.html), with the implementation using just a Hashtable and a boolean, take a look at the other post I linked here. Cheers, Marcelo.
Implement a trie with
insert, search, and startsWith methods.
Example:
Trie trie = new Trie();
trie.insert("apple");
trie.search("apple"); // returns true
trie.search("app"); // returns false
trie.startsWith("app"); // returns true
trie.insert("app");
trie.search("app"); // returns true
Note:
- You may assume that all inputs are consist of lowercase letters
a-z. - All inputs are guaranteed to be non-empty strings.
I've written about Tries before (https://anothercasualcoder.blogspot.com/2018/09/a-simple-trie-for-prefix-match-problem.html), with the implementation using just a Hashtable and a boolean, take a look at the other post I linked here. Cheers, Marcelo.
public class Trie
{
private Hashtable ht = null;
private bool endOfWord = false;
/** Initialize your data structure here. */
public Trie()
{
ht = new Hashtable();
endOfWord = false;
}
/** Inserts a word into the trie. */
public void Insert(string word)
{
if (String.IsNullOrEmpty(word)) this.endOfWord = true;
else if (ht.ContainsKey(word[0])) ((Trie)(ht[word[0]])).Insert(word.Substring(1));
else
{
Trie newTrie = new Trie();
ht.Add(word[0], newTrie);
((Trie)(ht[word[0]])).Insert(word.Substring(1));
}
}
/** Returns if the word is in the trie. */
public bool Search(string word)
{
if (String.IsNullOrEmpty(word)) return endOfWord;
else if (!ht.ContainsKey(word[0])) return false;
return ((Trie)(ht[word[0]])).Search(word.Substring(1));
}
/** Returns if there is any word in the trie that starts with the given prefix. */
public bool StartsWith(string prefix)
{
if (String.IsNullOrEmpty(prefix)) return true;
else if (!ht.ContainsKey(prefix[0])) return false;
return ((Trie)(ht[prefix[0]])).StartsWith(prefix.Substring(1));
}
}
Very nice. I usually end up using more space and time efficient data structures for storing children like arrays, but dictionaries are arguably super easy to deal with and support arbitrary characters out of the box.
ReplyDeleteC++ solution below:
class Trie {
private:
class Node {
private:
array children {nullptr};
bool terminal = false;
public:
Node*& child_at(char ch) {
return children[ch - 'a'];
}
void mark_as_terminal() { terminal = true; }
bool is_terminal() const { return terminal; }
};
Node* root;
Node* traverse(const string& word) {
Node* node = root;
for (int i = 0; i < word.size() && node != nullptr; ++i) {
node = node->child_at(word[i]);
}
return node;
}
public:
/** Initialize your data structure here. */
Trie(): root(new Node()) {}
/** Inserts a word into the trie. */
void insert(const string& word) {
Node* node = root;
for (char ch : word) {
auto& child = node->child_at(ch);
if (child == nullptr) child = new Node();
node = child;
}
node->mark_as_terminal();
}
/** Returns if the word is in the trie. */
bool search(const string& word) {
Node* node = traverse(word);
return node != nullptr && node->is_terminal();
}
/** Returns if there is any word in the trie that starts with the given prefix. */
bool startsWith(const string& prefix) {
Node* node = traverse(prefix);
return node != nullptr;
}
};