Trie

Question 1

208. Implement Trie (Prefix Tree)
     Implement a trie with insert, search, and startsWith methods.
     Example:
     Trie trie = new Trie();

trie.insert(“apple”);
trie.search(“apple”); // returns true
trie.search(“app”); // returns false
trie.startsWith(“app”); // returns true
trie.insert(“app”);
trie.search(“app”); // returns true
Note:
• You may assume that all inputs are consist of lowercase letters a-z.
• All inputs are guaranteed to be non-empty strings.
TC –
SC –

Answer 1

Pseudo code:

1. Define a class Trie.
2. Trie class will have below two variable
   i. Array of type trie class named children.
   ii. Boolean variable named as isEndOfWord.
3. Trie class will have below methods:
   i. Insert, search, startWith.
4. Insert Method:
   i. We will declare a instance variable of Trie class and assign to current class object (this).
   ii. Loop through the string from input for each character. Will take char variable named as ch for each character.
   iii. If curr object have children on (ch – ‘a’) index, we will assign that to curr and move forward on next iteration.
   iv. Else we will create a new Trie object and will assign to curr object children on (ch – ‘a’). Assign new object to curr and move forward on next iteration.
   v. Outside loop will update isEndOfWord to true.
5. Search Method:
   i. We will declare a instance variable of Trie class and assign to this object.
   ii. Loop through the string from input for each character. Will take char variable named as ch for each character.
   iii. If curr object have children on (ch – ‘a’) index then move on next iteration otherwise return false.
   iv. Outside loop return curr.isEndOfWord.
6. startWith Method:
   i. We will declare a instance variable of Trie class and assign to this object.
   ii. Loop through the string from input for each character. Will take char variable named as ch for each character.
   iii. If curr object have children on (ch – ‘a’) index then move on next iteration otherwise return false.
   iv. Outside loop return true.

class Trie {

      /** Initialize your data structure here. */
	Trie[] children;
	boolean isEndOfWord;
    public Trie() {
       children = new Trie[26];
       isEndOfWord = false;
    }

    /** Inserts a word into the trie. */
    public void insert(String word) {
    	Trie curr = this;
    	for(char c : word.toCharArray()) {
    		if(curr.children[c - 'a']==null) {
    			curr.children[c - 'a'] = new Trie();
    		}
    		curr = curr.children[c - 'a'];
    	}
    	curr.isEndOfWord = true;
    }

    /** Returns if the word is in the trie. */
    public boolean search(String word) {
    	Trie curr = this;
    	for(char c : word.toCharArray()) {
    		curr = curr.children[c - 'a'];
    		if(curr==null) {
    			return false;
    		}
    	}
    	if(curr.isEndOfWord) {
    		return true;
    	}
    	return false;
    }

    /** Returns if there is any word in the trie that starts with the given prefix. */
    public boolean startsWith(String prefix) {
    	Trie curr = this;
    	for(char c : prefix.toCharArray()) {
    		curr = curr.children[c - 'a'];
    		if(curr==null) {
    			return false;
    		}
    	}
    	return true;
    }
}