Created
May 31, 2022 18:52
-
-
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/)
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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