Skip to content

Instantly share code, notes, and snippets.

@mustafa-qamaruddin
Created May 31, 2022 18:52
Show Gist options
  • Save mustafa-qamaruddin/25acc1cb16d8bce6b387fabf6406019b to your computer and use it in GitHub Desktop.
Save mustafa-qamaruddin/25acc1cb16d8bce6b387fabf6406019b to your computer and use it in GitHub Desktop.
Trie Data Structure - Recursive Search ( LeetCode 211. Design Add and Search Words Data Structure) https://leetcode.com/problems/design-add-and-search-words-data-structure/)
class Trie {
TrieNode root;
public Trie() {
root = new TrieNode();
}
public TrieNode getRoot() {
return root;
}
public void insert(String word) {
TrieNode currNode = root;
for (int i = 0; i < word.length(); i++) {
char c = word.charAt(i);
if (!currNode.containsKey(c)) {
currNode.put(c, new TrieNode());
}
currNode = currNode.get(c);
}
currNode.setEnd();
}
TrieNode searchPrefix(String word) {
TrieNode currNode = root;
for (int i = 0; i < word.length(); i++) {
char c = word.charAt(i);
if (!currNode.containsKey(c)) {
return null;
}
currNode = currNode.get(c);
}
return currNode;
}
public boolean search(String word) {
TrieNode node = searchPrefix(word);
return node != null && node.isEnd();
}
public boolean startsWith(String prefix) {
return searchPrefix(prefix) != null;
}
public boolean genSearch(char[] chars, int idx, TrieNode currNode) {
// edge case: if the trie is consumed before the word is consume???
if (idx < chars.length && currNode == null) return false;
// base case: word consumed
if (idx >= chars.length) return true;
char currChar = chars[idx];
// char found: success and next
if (currNode != null && currNode.containsKey(currChar)) {
return genSearch(chars, idx + 1, currNode.get(currChar));
}
// dot found: consume next (unless next is null)
if (currChar == '.' && currNode != null) {
for (int j = 0; j < currNode.numChildren(); j++) {
// any filled link from currNode
if (currNode.get(j) != null) {
// the branch consumed the reminder successfully?
if (genSearch(chars, idx + 1, currNode.get(j))) {
return true;
}
}
}
}
// else
return false;
}
private class TrieNode {
final int R = 128;
char value;
boolean isEndKey;
TrieNode[] children;
public TrieNode() {
children = new TrieNode[R];
}
public boolean containsKey(int c) {
return children[c] != null;
}
public TrieNode get(int c) {
return children[c];
}
public void put(int c, TrieNode node) {
children[c] = node;
}
public void setEnd() {
isEndKey = true;
}
public boolean isEnd() {
return isEndKey;
}
public int numChildren() {
return R;
}
}
}
/**
* 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);
*/
class WordDictionary {
Trie trie;
public WordDictionary() {
trie = new Trie();
}
public void addWord(String word) {
trie.insert(word);
}
public boolean search(String word) {
char[] chars = word.toCharArray();
return trie.genSearch(chars, 0, trie.getRoot());
}
}
/**
* Your WordDictionary object will be instantiated and called as such:
* WordDictionary obj = new WordDictionary();
* obj.addWord(word);
* boolean param_2 = obj.search(word);
*/
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment