add 1268

fishercoder1534 · fishercoder1534 · commit 29089bb9475a · 2020-11-18T10:40:31.000-08:00
diff --git a/README.md b/README.md
@@ -187,6 +187,7 @@ _If you like this project, please leave me a star._ &#9733;
 |1275|[Find Winner on a Tic Tac Toe Game](https://leetcode.com/problems/find-winner-on-a-tic-tac-toe-game/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_1275.java) |   |Easy|Array|
 |1273|[Delete Tree Nodes](https://leetcode.com/problems/delete-tree-nodes/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_1273.java) |   |Medium|Dynamic Programming, DFS |
 |1271|[Hexspeak](https://leetcode.com/problems/hexspeak/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_1271.java) |   |Easy||
+|1268|[Search Suggestions System](https://leetcode.com/problems/search-suggestions-system/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_1268.java) |   |Medium|String|
 |1267|[Count Servers that Communicate](https://leetcode.com/problems/count-servers-that-communicate/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_1267.java) |   |Medium||
 |1266|[Minimum Time Visiting All Points](https://leetcode.com/problems/minimum-time-visiting-all-points/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_1266.java) |   |Easy||
 |1265|[Print Immutable Linked List in Reverse](https://leetcode.com/problems/print-immutable-linked-list-in-reverse//)|[Solution](../master/src/main/java/com/fishercoder/solutions/_1265.java) |   |Medium||
diff --git a/src/main/java/com/fishercoder/solutions/_1268.java b/src/main/java/com/fishercoder/solutions/_1268.java
@@ -0,0 +1,88 @@
+package com.fishercoder.solutions;
+
+import java.util.ArrayList;
+import java.util.List;
+
+public class _1268 {
+    public static class Solution1 {
+        public List<List<String>> suggestedProducts(String[] products, String searchWord) {
+            TrieNode root = buildTrie(products);
+            List<List<String>> result = new ArrayList<>();
+            for (int i = 1; i <= searchWord.length(); i++) {
+                String searchTerm = searchWord.substring(0, i);
+                result.add(findTopThreeMatches(root, searchTerm));
+            }
+            return result;
+        }
+
+        private List<String> findTopThreeMatches(TrieNode root, String searchTerm) {
+            List<String> result = new ArrayList<>();
+            TrieNode node = root;
+            for (char c : searchTerm.toCharArray()) {
+                if (node.children[c - 'a'] == null) {
+                    return result;
+                } else {
+                    node = node.children[c - 'a'];
+                }
+            }
+            if (node.isWord) {
+                result.add(searchTerm);
+            }
+            for (TrieNode child : node.children) {
+                if (child != null) {
+                    List<String> thisResult = dfs(child, searchTerm, new ArrayList<>());
+                    result.addAll(thisResult);
+                    if (result.size() >= 3) {
+                        return result.subList(0, 3);
+                    }
+                }
+            }
+            return result;
+        }
+
+        private List<String> dfs(TrieNode node, String substring, List<String> result) {
+            if (node.isWord) {
+                result.add(substring + node.c);
+                if (result.size() >= 3) {
+                    return result;
+                }
+            }
+            for (TrieNode child : node.children) {
+                if (child != null) {
+                    dfs(child, substring + node.c, result);
+                }
+            }
+            return result;
+        }
+
+        private TrieNode buildTrie(String[] products) {
+            TrieNode root = new TrieNode(' ');
+            for (String pro : products) {
+                insert(pro, root);
+            }
+            return root;
+        }
+
+        private void insert(String word, TrieNode root) {
+            TrieNode node = root;
+            for (int i = 0; i < word.length(); i++) {
+                char c = word.charAt(i);
+                if (node.children[c - 'a'] == null) {
+                    node.children[c - 'a'] = new TrieNode(c);
+                }
+                node = node.children[c - 'a'];
+            }
+            node.isWord = true;
+        }
+
+        class TrieNode {
+            TrieNode[] children = new TrieNode[26];
+            boolean isWord;
+            char c;
+
+            public TrieNode(char c) {
+                this.c = c;
+            }
+        }
+    }
+}
diff --git a/src/test/java/com/fishercoder/_1268Test.java b/src/test/java/com/fishercoder/_1268Test.java
@@ -0,0 +1,28 @@
+package com.fishercoder;
+
+import com.fishercoder.solutions._1268;
+import org.junit.BeforeClass;
+import org.junit.Test;
+
+import java.util.Arrays;
+import java.util.List;
+
+import static org.junit.Assert.assertEquals;
+
+public class _1268Test {
+    private static _1268.Solution1 solution1;
+    private static List<List<String>> expected;
+    private static String[] products;
+
+    @BeforeClass
+    public static void setup() {
+        solution1 = new _1268.Solution1();
+    }
+
+    @Test
+    public void test1() {
+        products = new String[]{"mobile", "mouse", "moneypot", "monitor", "mousepad"};
+        expected = Arrays.asList(Arrays.asList("mobile", "moneypot", "monitor"), Arrays.asList("mobile", "moneypot", "monitor"), Arrays.asList("mouse", "mousepad"), Arrays.asList("mouse", "mousepad"), Arrays.asList("mouse", "mousepad"));
+        assertEquals(expected, solution1.suggestedProducts(products, "mouse"));
+    }
+}
