208. Implement Trie (Prefix Tree)

https://leetcode.com/problems/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.

---

Related problems

211-add-and-search-word-data-structure

---

	class TrieNode {
	TrieNode[] children;
	boolean isWord;
	public TrieNode() {
	this.children = new TrieNode[26];
	this.isWord = false;
	}
	}
	class Trie {
	TrieNode root;
	/** Initialize your data structure here. */
	public Trie() {
	this.root = new TrieNode();
	}
	/** Inserts a word into the trie. */
	public void insert(String word) {
	TrieNode current = this.root;
	for (int i = 0; i < word.length(); i++) {
	if (current.children[word.charAt(i) - 'a'] == null) {
	current.children[word.charAt(i) - 'a'] = new TrieNode();
	}
	current = current.children[word.charAt(i) - 'a'];
	}
	current.isWord = true;
	}
	/** Returns if the word is in the trie. */
	public boolean search(String word) {
	TrieNode current = this.root;
	for (int i = 0; i < word.length(); i++) {
	if (current.children[word.charAt(i) - 'a'] == null) {
	return false;
	}
	current = current.children[word.charAt(i) - 'a'];
	}
	return current.isWord == true;
	}
	/** Returns if there is any word in the trie that starts with the given prefix. */
	public boolean startsWith(String prefix) {
	TrieNode current = this.root;
	for (int i = 0; i < prefix.length(); i++) {
	if (current.children[prefix.charAt(i) - 'a'] == null) {
	return false;
	}
	current = current.children[prefix.charAt(i) - 'a'];
	}
	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);
	*/

view raw 208.ImplementTrie(PrefixTree).java hosted with ❤ by GitHub