Implement Trie
Question
Implement a trie with insert, search, and startsWith methods.
Note:
You may assume that all inputs are consist of lowercase letters a-z.
Analysis
https://leetcode.com/articles/implement-trie-prefix-tree/
Trie Node Definition
class TrieNode {
// R links to node children
private TrieNode[] links;
private final int R = 26;
private boolean isEnd;
public TrieNode() {
links = new TrieNode[R];
}
public boolean containsKey(char ch) {
return links[ch -'a'] != null;
}
public TrieNode get(char ch) {
return links[ch -'a'];
}
public void put(char ch, TrieNode node) {
links[ch -'a'] = node;
}
public void setEnd() {
isEnd = true;
}
public boolean isEnd() {
return isEnd;
}
}class Trie {
private TrieNode root;
public Trie() {
root = new TrieNode();
}
// Inserts a word into the trie.
public void insert(String word) {
TrieNode node = root;
for (int i = 0; i < word.length(); i++) {
char currentChar = word.charAt(i);
if (!node.containsKey(currentChar)) {
node.put(currentChar, new TrieNode());
}
node = node.get(currentChar);
}
node.setEnd();
}
// search a prefix or whole key in trie and
// returns the node where search ends
private TrieNode searchPrefix(String word) {
TrieNode node = root;
for (int i = 0; i < word.length(); i++) {
char curLetter = word.charAt(i);
if (node.containsKey(curLetter)) {
node = node.get(curLetter);
} else {
return null;
}
}
return node;
}
// Returns if the word is in the trie.
public boolean search(String word) {
TrieNode node = searchPrefix(word);
return node != null && node.isEnd();
}
// Returns if there is any word in the trie
// that starts with the given prefix.
public boolean startsWith(String prefix) {
TrieNode node = searchPrefix(prefix);
return node != null;
}
}Solution
Implementation 1 - using hashmap for characters
A trie node should contains the character, its children and the flag that marks if it is a leaf node. You can use this diagram to walk though the Java solution.
class TrieNode {
// Initialize your data structure here.
char c;
HashMap<Character, TrieNode> children = new HashMap<Character, TrieNode>();
boolean isLeaf;
public TrieNode() {}
public TrieNode(char c) {
this.c = c;
}
}
public class Trie {
private TrieNode root;
public Trie() {
root = new TrieNode();
}
// Inserts a word into the trie.
public void insert(String word) {
HashMap<Character, TrieNode> children = root.children;
for (int i = 0; i < word.length(); i++) {
char c = word.charAt(i);
TrieNode t;
if (children.containsKey(c)) {
t = children.get(c);
} else {
t = new TrieNode(c);
children.put(c, t);
}
children = t.children;
// Set leaf node
if (i == word.length() - 1) {
t.isLeaf = true;
}
}
}
// Returns if the word is in the trie.
public boolean search(String word) {
TrieNode t = searchNode(word);
if (t != null && t.isLeaf) {
return true;
} else {
return false;
}
}
// Returns if there is any word in the trie
// that starts with the given prefix.
public boolean startsWith(String prefix) {
if (searchNode(prefix) == null) {
return false;
} else {
return true;
}
}
// Search a String in Trie, return TrieNode if exists
public TrieNode searchNode(String str) {
HashMap<Character, TrieNode> children = root.children;
TrieNode t = null;
for (int i = 0; i < str.length(); i++) {
char c = str.charAt(i);
if (children.containsKey(c)) {
t = children.get(c);
children = t.children;
} else {
return null;
}
}
return t;
}
}
// Your Trie object will be instantiated and called as such:
// Trie trie = new Trie();
// trie.insert("somestring");
// trie.search("key");LeetCode official solution
class Trie {
class TrieNode {
public boolean isWord;
public Map<Character, TrieNode> childrenMap = new HashMap<>();
}
private TrieNode root;
/** Initialize your data structure here. */
public Trie() {
root = new TrieNode();
}
/** Inserts a word into the trie. */
public void insert(String word) {
TrieNode cur = root;
for(int i = 0; i < word.length(); i++){
char c = word.charAt(i);
if(cur.childrenMap.get(c) == null){
// insert a new node if the path does not exist
cur.childrenMap.put(c, new TrieNode());
}
cur = cur.childrenMap.get(c);
}
cur.isWord = true;
}
/** Returns if the word is in the trie. */
public boolean search(String word) {
TrieNode cur = root;
for(int i = 0; i < word.length(); i++) {
char c = word.charAt(i);
if(cur.childrenMap.get(c) == null) {
return false;
}
cur = cur.childrenMap.get(c);
}
return cur.isWord;
}
/** Returns if there is any word in the trie that starts with the given prefix. */
public boolean startsWith(String prefix) {
TrieNode cur = root;
for(int i = 0;i < prefix.length(); i++){
char c = prefix.charAt(i);
if(cur.childrenMap.get(c) == null) {
return false;
}
cur = cur.childrenMap.get(c);
}
return true;
}
}Java Implementation 2 - Using array for characters
Each trie node can only contains 'a'-'z' characters. So we can use a small array to store the character.
class TrieNode {
TrieNode[] arr;
boolean isEnd;
// Initialize your data structure here.
public TrieNode() {
this.arr = new TrieNode[26];
}
}
public class Trie {
private TrieNode root;
public Trie() {
root = new TrieNode();
}
// Inserts a word into the trie.
public void insert(String word) {
TrieNode p = root;
for(int i=0; i<word.length(); i++){
char c = word.charAt(i);
int index = c-'a';
if(p.arr[index]==null){
TrieNode temp = new TrieNode();
p.arr[index]=temp;
p = temp;
}else{
p=p.arr[index];
}
}
p.isEnd=true;
}
// Returns if the word is in the trie.
public boolean search(String word) {
TrieNode p = searchNode(word);
if(p==null){
return false;
}else{
if(p.isEnd)
return true;
}
return false;
}
// Returns if there is any word in the trie
// that starts with the given prefix.
public boolean startsWith(String prefix) {
TrieNode p = searchNode(prefix);
if(p==null){
return false;
}else{
return true;
}
}
public TrieNode searchNode(String s){
TrieNode p = root;
for(int i=0; i<s.length(); i++){
char c= s.charAt(i);
int index = c-'a';
if(p.arr[index]!=null){
p = p.arr[index];
}else{
return null;
}
}
if(p==root)
return null;
return p;
}
}Reference
Last updated