Prefix and Suffix Search: Accepted

gouthampradhan · gouthampradhan · commit 76d0ee345974 · 2017-12-26T03:19:18.000+05:30
diff --git a/README.md b/README.md
@@ -100,6 +100,7 @@ My accepted leetcode solutions to some of the common interview problems.
 - [Design Excel Sum Formula](problems/src/design/Excel.java) (Hard)
 - [Flatten Nested List Iterator](problems/src/design/NestedIterator.java) (Medium)
 - [Add and Search Word - Data structure design](problems/src/design/WordDictionary.java) (Medium)
+- [Prefix and Suffix Search](problems/src/design/WordFilter.java) (Hard)
 
 #### [Divide and Conquer](problems/src/divide_and_conquer)
 
diff --git a/problems/src/design/WordFilter.java b/problems/src/design/WordFilter.java
@@ -0,0 +1,124 @@
+package design;
+
+import java.util.HashMap;
+import java.util.Map;
+
+/**
+ * Created by gouthamvidyapradhan on 25/12/2017.
+ * Given many words, words[i] has weight i.
+
+ Design a class WordFilter that supports one function, WordFilter.f(String prefix, String suffix). It will return the
+ word with given prefix and suffix with maximum weight. If no word exists, return -1.
+
+ Examples:
+ Input:
+ WordFilter(["apple"])
+ WordFilter.f("a", "e") // returns 0
+ WordFilter.f("b", "") // returns -1
+ Note:
+ words has length in range [1, 15000].
+ For each test case, up to words.length queries WordFilter.f may be made.
+ words[i] has length in range [1, 10].
+ prefix, suffix have lengths in range [0, 10].
+ words[i] and prefix, suffix queries consist of lowercase letters only.
+
+ Solution: Implement a trie to store the dictionary of words. For every word insert all the possible suffixes into
+ the trie. Additionally overwrite weight each time a word is inserted.
+ Example for a word 'cat' all the possible trie insertions are -> #cat, t#cat, at#cat, cat#cat
+ Search for 'suffix#prefix' in the trie and return its weight
+ */
+public class WordFilter {
+
+    private Trie trie;
+    private int maxWeight; //max weight possible
+    /**
+     * Main method
+     *
+     * @param args
+     * @throws Exception
+     */
+    public static void main(String[] args) throws Exception {
+        String[] words = {"apple", "cat", "mat", "mars", "abxcd", "abycd", "apple"};
+        WordFilter wf = new WordFilter(words);
+        System.out.println(wf.f("abx", ""));
+    }
+
+    public WordFilter(String[] words) {
+        trie = new Trie();
+        trie.weight = -1;
+        maxWeight = words.length - 1;
+        for(int i = 0; i < words.length; i ++){
+            String word = words[i];
+            trie.insert("#" + word, i);
+            for(int j = 0, l = word.length(); j < l; j++){
+                trie.insert(word.substring(j, l) + "#" + word, i);
+            }
+        }
+    }
+
+    public int f(String prefix, String suffix) {
+        if((suffix == null || suffix.isEmpty()) && (prefix == null || prefix.isEmpty())){
+            return maxWeight;
+        } else if(prefix == null || prefix.isEmpty()){
+            return trie.search(suffix + "#");
+        } else if(suffix == null || suffix.isEmpty()){
+            return trie.search("#" + prefix);
+        } else{
+            return trie.search(suffix + "#" + prefix);
+        }
+    }
+
+    public static class Trie {
+
+        private Map<Character, Trie> map;
+        int weight;
+
+
+        /**
+         * Initialize your data structure here.
+         */
+        public Trie() {
+            map = new HashMap<>();
+        }
+
+        /**
+         * Inserts a word into the trie.
+         */
+        public void insert(String word, int weight) {
+            if (word != null) {
+                add(0, word, word.length(), weight);
+            }
+        }
+
+        private void add(int i, String word, int length, int weight) {
+            if (i < length) {
+                char c = word.charAt(i);
+                map.putIfAbsent(c, new Trie());
+                Trie subTrie = map.get(c);
+                subTrie.weight = weight;
+                subTrie.add(i + 1, word, length, weight);
+            }
+        }
+
+        /**
+         * Returns if the word is in the trie.
+         */
+        public int search(String word) {
+            if (word != null) {
+                return search(0, word, word.length());
+            }
+            return -1;
+        }
+
+        private int search(int i, String word, int length) {
+            if (i < length) {
+                char c = word.charAt(i);
+                Trie subTrie = map.get(c);
+                if (subTrie == null)
+                    return -1;
+                return subTrie.search(i + 1, word, length);
+            }
+            return this.weight;
+        }
+    }
+}
