Updated Design Add and Search Words Data Structure

varunu28 · varunu28 · commit f3c457c2327a · 2023-03-18T18:16:35.000-07:00
diff --git a/Medium/Design Add and Search Words Data Structure.java b/Medium/Design Add and Search Words Data Structure.java
@@ -1,54 +1,53 @@
 class WordDictionary {
-  
-  private Node root;
-  
-  public WordDictionary() {
-    this.root = new Node();
-  }
-
-  public void addWord(String word) {
-    Node curr = root;
-    for (char c : word.toCharArray()) {
-      if (curr.children[c - 'a'] == null) {
-        curr.children[c - 'a'] = new Node();
-      }
-      curr = curr.children[c - 'a'];
+
+    private final TrieNode root;
+
+    public WordDictionary() {
+        this.root = new TrieNode();
     }
-    curr.isWord = true;
-  }
-
-  public boolean search(String word) {
-    Node curr = root;
-    return searchHelper(word, 0, curr);
-  }
-  
-  private boolean searchHelper(String word, int idx, Node curr) {
-    if (idx == word.length()) {
-      return curr.isWord;
+
+    public void addWord(String word) {
+        TrieNode curr = root;
+        for (char c : word.toCharArray()) {
+            if (!curr.children.containsKey(c)) {
+                curr.children.put(c, new TrieNode());
+            }
+            curr = curr.children.get(c);
+        }
+        curr.isWord = true;
     }
-    if (word.charAt(idx) != '.' && curr.children[word.charAt(idx) - 'a'] == null) {
-      return false;
+
+    public boolean search(String word) {
+        return searchHelper(word, 0, root);
     }
-    if (word.charAt(idx) == '.') {
-      for (Node child : curr.children) {
-        if (child != null && searchHelper(word, idx + 1, child)) {
-          return true;
+
+    private boolean searchHelper(String word, int idx, TrieNode node) {
+        if (idx == word.length()) {
+            return node.isWord;
         }
-      }
-      return false;
+        if (node.children.containsKey(word.charAt(idx))) {
+            return searchHelper(word, idx + 1, node.children.get(word.charAt(idx)));
+        }
+        if (word.charAt(idx) == '.') {
+            for (TrieNode child : node.children.values()) {
+                if (searchHelper(word, idx + 1, child)) {
+                    return true;
+                }
+            }
+        }
+        return false;
     }
-    return searchHelper(word, idx + 1, curr.children[word.charAt(idx) - 'a']);
-  }
-  
-  private static class Node {
-    Node[] children;
-    boolean isWord;
-    
-    public Node() {
-      this.children = new Node[26];
-      this.isWord = false;
+
+
+    static class TrieNode {
+        private final Map<Character, TrieNode> children;
+        private boolean isWord;
+
+        public TrieNode() {
+            this.children = new HashMap<>();
+            this.isWord = false;
+        }
     }
-  }
 }
 
 /**
