Implement a trie with
Example:
Note:
- You may assume that all inputs are consist of lowercase letters
a-z . - All inputs are guaranteed to be non-empty strings.
Solution
Trie is a N-Ary tree with property like every node have max 26 child nodes. Store Words from the root to the leaf node and make leaf node as
Code
|
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 |
import java.util.HashMap; import java.util.Map; public class Trie { private TrieNode root; public Trie() { root = new TrieNode(); } /** Inserts a word into the trie. */ public void insert(String s) { TrieNode current = root; for (int i = 0; i < s.length(); i++) { char ch = s.charAt(i); TrieNode node = current.children.get(ch); if (node == null) { node = new TrieNode(); current.children.put(ch, node); } current = node; } current.endOfWord = true; } /** Returns if the word is in the trie. */ public boolean search(String s) { TrieNode current = root; for (int i = 0; i < s.length(); i++) { //iterate through the word and check if its present in Trie char ch = s.charAt(i); TrieNode node = current.children.get(ch); if (node == null) return false; current = node; } return current.endOfWord ? true : false; } /** * Returns if there is any word in the trie that starts with the given prefix. */ public boolean startsWith(String s) { TrieNode current = root; for (int i = 0; i < s.length(); i++) { //iterate through the word and check if its present in Trie char ch = s.charAt(i); TrieNode node = current.children.get(ch); if (node == null) return false; current = node; } return true; } public static void main(String[] args) { Trie trieObj=new Trie(); trieObj.insert("Dog"); trieObj.insert("Deer"); System.out.println(trieObj.search("Dog")); System.out.println(trieObj.startsWith("Do")); System.out.println(trieObj.startsWith("w")); } } class TrieNode { Map<Character, TrieNode> children; boolean endOfWord; TrieNode() { children = new HashMap<Character, TrieNode>(); endOfWord = false; } } |
Output
We encourage you to write a comment if you have a better solution or having any doubt on the above topic.
 "Pinterest"){kind=logo}
