208 Implement Trie (Prefix Tree)¶
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
C# Solution¶
using System;
using System.Collections.Generic;
namespace Algorithms.Medium
{
public class TrieNode
{
public Dictionary<char, TrieNode> children;
public bool endOfWord;
public TrieNode()
{
children = new Dictionary<char, TrieNode>();
endOfWord = false;
}
}
public class Trie
{
public TrieNode root { get; private set; }
public Trie()
{
root = new TrieNode();
}
public void Insert(string v)
{
var current = root;
for (var i = 0; i < v.Length; i++)
{
if (!current.children.ContainsKey(v[i]))
{
current.children.Add(v[i], new TrieNode());
}
current = current.children[v[i]];
}
current.endOfWord = true;
}
public virtual bool Search(string v, bool isStartsWith = false)
{
var current = root;
for (var i = 0; i < v.Length; i++)
{
if (!current.children.ContainsKey(v[i])) return false;
current = current.children[v[i]];
}
return isStartsWith ? true : current.endOfWord;
}
public bool StartsWith(string v)
{
return Search(v, true);
}
}
}
C# Tests¶
using Algorithms.Medium;
using Xunit;
namespace AlgorithmTests.Medium
{
public class TrieNodeTests
{
[Fact]
public void TestTrie()
{
Trie trie = new Trie();
trie.Insert("apple");
Assert.True(trie.Search("apple"));
Assert.False(trie.Search("app"));
Assert.True(trie.StartsWith("app"));
trie.Insert("app");
Assert.True(trie.Search("app"));
}
}
}