Top data structure used in String related
A really useful yet not so used data structure is a Trie. We can see a Trie as a tree that contains a character value and a boolean flag to state weather we accomplished a word or not.
It helps you to save space as strings with same prefix will be under similar paths. It can be found in several pages with interview exercises such as leetcode, hackerrank, algoexpert, interviewio and others.
In the next post we find my Trie implementation with methods:
- Constructor()
- insert(String)
- search(String)
- startsWith(String)
class Trie {/** Initialize your data structure here. */private class TrieNode{
Character val;
HashMap<Character, TrieNode> childs;
Boolean isWord;
public TrieNode(){
this.isWord=false;
this.childs = new HashMap<Character, TrieNode>();
this.val=null;
}
}
TrieNode root;
public Trie() {
this.root = new TrieNode();
}
/** Inserts a word into the trie. */
public void insert(String word) {
TrieNode node =root;
for(Character c: word.toCharArray()){
if(node.childs.get(c)==null ){
node.childs.put(c, new TrieNode() );
}
node = node.childs.get(c);
}
node.isWord=true;
}
/** Returns if the word is in the trie. */
public boolean search(String word) {
TrieNode node =root;
for(Character c: word.toCharArray()){
if(node.childs.get(c)==null ) return false;
node = node.childs.get(c);
}
return node.isWord;
}
/** Returns if there is any word in the trie that starts with the given prefix. */
public boolean startsWith(String prefix) {
TrieNode node =root;
for(Character c: prefix.toCharArray()){
if(node.childs.get(c)==null ) return false;
node = node.childs.get(c);
}
return true;
}
}
/**
* 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);
*/
