add 1804

fishercoder1534 · fishercoder1534 · commit 48d17b0d6729 · 2021-10-09T10:11:18.000-07:00
diff --git a/README.md b/README.md
@@ -84,6 +84,7 @@ _If you like this project, please leave me a star._ &#9733;
 |1807|[Evaluate the Bracket Pairs of a String](https://leetcode.com/problems/evaluate-the-bracket-pairs-of-a-string/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_1807.java) ||Medium|HashTable, String|
 |1806|[Minimum Number of Operations to Reinitialize a Permutation](https://leetcode.com/problems/minimum-number-of-operations-to-reinitialize-a-permutation/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_1806.java) ||Medium|Array, Greedy|
 |1805|[Number of Different Integers in a String](https://leetcode.com/problems/number-of-different-integers-in-a-string/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_1805.java) ||Medium|String|
+|1804|[Implement Trie II (Prefix Tree)](https://leetcode.com/problems/implement-trie-ii-prefix-tree/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_1804.java) ||Medium|Trie, Design|
 |1800|[Maximum Ascending Subarray Sum](https://leetcode.com/problems/maximum-ascending-subarray-sum/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_1800.java) ||Easy|Two Pointers|
 |1797|[Design Authentication Manager](https://leetcode.com/problems/design-authentication-manager/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_1797.java) ||Medium|HashTable, Design|
 |1796|[Second Largest Digit in a String](https://leetcode.com/problems/second-largest-digit-in-a-string/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_1796.java) ||Easy|String|
diff --git a/src/main/java/com/fishercoder/solutions/_1804.java b/src/main/java/com/fishercoder/solutions/_1804.java
@@ -0,0 +1,75 @@
+package com.fishercoder.solutions;
+
+public class _1804 {
+    public static class Solution1 {
+        public static class Trie {
+            class TrieNode {
+                int count;
+                int wordsCount;
+                TrieNode[] children;
+
+                public TrieNode() {
+                    this.children = new TrieNode[26];
+                }
+
+                boolean isWord;
+            }
+
+            TrieNode root;
+
+            public Trie() {
+                root = new TrieNode();
+            }
+
+            public void insert(String word) {
+                TrieNode node = this.root;
+                for (char c : word.toCharArray()) {
+                    if (node.children[c - 'a'] == null) {
+                        node.children[c - 'a'] = new TrieNode();
+                    }
+                    if (node.children[c - 'a'].count < 0) {
+                        node.children[c - 'a'].count = 0;
+                    }
+                    node.children[c - 'a'].count++;
+                    node = node.children[c - 'a'];
+                }
+                node.isWord = true;
+                if (node.wordsCount < 0) {
+                    node.wordsCount = 0;
+                }
+                node.wordsCount++;
+            }
+
+            public int countWordsEqualTo(String word) {
+                TrieNode node = this.root;
+                for (char c : word.toCharArray()) {
+                    if (node.children[c - 'a'] == null) {
+                        return 0;
+                    }
+                    node = node.children[c - 'a'];
+                }
+                return node.isWord ? node.wordsCount : 0;
+            }
+
+            public int countWordsStartingWith(String prefix) {
+                TrieNode node = this.root;
+                for (char c : prefix.toCharArray()) {
+                    if (node.children[c - 'a'] == null) {
+                        return 0;
+                    }
+                    node = node.children[c - 'a'];
+                }
+                return node.count < 0 ? 0 : node.count;
+            }
+
+            public void erase(String word) {
+                TrieNode node = this.root;
+                for (char c : word.toCharArray()) {
+                    node.children[c - 'a'].count--;
+                    node = node.children[c - 'a'];
+                }
+                node.wordsCount--;
+            }
+        }
+    }
+}
diff --git a/src/test/java/com/fishercoder/_1804Test.java b/src/test/java/com/fishercoder/_1804Test.java
@@ -0,0 +1,31 @@
+package com.fishercoder;
+
+import com.fishercoder.solutions._1804;
+import org.junit.BeforeClass;
+import org.junit.Test;
+
+import static org.junit.Assert.assertEquals;
+
+public class _1804Test {
+    private static _1804.Solution1.Trie solution1;
+
+    @BeforeClass
+    public static void setup() {
+
+    }
+
+    @Test
+    public void test1() {
+        solution1 = new _1804.Solution1.Trie();
+        solution1.insert("apple");
+        solution1.insert("apple");
+        assertEquals(2, solution1.countWordsEqualTo("apple"));
+        assertEquals(2, solution1.countWordsStartingWith("app"));
+        solution1.erase("apple");
+        assertEquals(1, solution1.countWordsEqualTo("apple"));
+        assertEquals(1, solution1.countWordsStartingWith("app"));
+        solution1.erase("apple");
+        assertEquals(0, solution1.countWordsStartingWith("app"));
+    }
+
+}
