@@ -0,0 +1,2886 @@
+package leetcode;%0A%0A/**%0A * https://leetcode.com/problems/prefix-and-suffix-search/%0A */%0Apublic class Problem745 %7B%0A    static class WordFilter %7B%0A        private final Node%5B%5D nodes = new Node%5B27%5D; // extra one char for separator%0A%0A        private static class Node %7B%0A            private int weight;%0A            private final Node%5B%5D children = new Node%5B27%5D; // extra one char for separator%0A        %7D%0A%0A        public WordFilter(String%5B%5D words) %7B%0A            int weight = 0;%0A            for (String word : words) %7B%0A                for (int i = word.length(); i %3E= 0; i--) %7B%0A                    // We choose '%7B' because it's a character after z.%0A                    String newWord = word.substring(i) + %22%7B%22 + word;%0A                    int index = 0;%0A                    Node node = nodes%5BnewWord.charAt(index) - 'a'%5D;%0A                    if (node == null) %7B%0A                        node = new Node();%0A                        nodes%5BnewWord.charAt(index) - 'a'%5D = node;%0A                    %7D%0A                    node.weight = weight;%0A                    insert(newWord, index + 1, node);%0A                %7D%0A                weight++;%0A            %7D%0A        %7D%0A%0A        public int f(String prefix, String suffix) %7B%0A            String word = suffix + %22%7B%22 + prefix;%0A            int index = 0;%0A            Node node = nodes%5Bword.charAt(index) - 'a'%5D;%0A            if (node == null) %7B%0A                return -1;%0A            %7D%0A            return search(word, index + 1, node);%0A        %7D%0A%0A        private static void insert(String word, int i, Node node) %7B%0A            if (i == word.length()) %7B%0A                return;%0A            %7D%0A            Node child = node.children%5Bword.charAt(i) - 'a'%5D;%0A            if (child == null) %7B%0A                child = new Node();%0A                node.children%5Bword.charAt(i) - 'a'%5D = child;%0A            %7D%0A            child.weight = node.weight;%0A            insert(word, i + 1, child);%0A        %7D%0A%0A        private static int search(String word, int i, Node node) %7B%0A            if (i == word.length()) %7B%0A                return node.weight;%0A            %7D%0A            Node child = node.children%5Bword.charAt(i) - 'a'%5D;%0A            if (node == null) %7B%0A                return -1;%0A            %7D%0A            return search(word, i + 1, child);%0A        %7D%0A    %7D%0A%0A    public static void main(String%5B%5D args) %7B%0A        WordFilter wf = new WordFilter(new String%5B%5D%7B%22apple%22, %22facebook%22, %22fakebook%22%7D);%0A        System.out.println(wf.f(%22a%22, %22e%22)); // 0%0A        System.out.println(wf.f(%22fa%22, %22ook%22)); // 1%0A%0A//        WordFilter wf = new WordFilter(new String%5B%5D%7B%0A//            %22cabaabaaaa%22,%22ccbcababac%22,%22bacaabccba%22,%22bcbbcbacaa%22,%22abcaccbcaa%22,%22accabaccaa%22,%22cabcbbbcca%22,%22ababccabcb%22,%22caccbbcbab%22,%22bccbacbcba%22%0A//        %7D);%0A//        System.out.println(wf.f(%22bccbacbcba%22,%22a%22)); // 9%0A//        System.out.println(wf.f(%22ab%22,%22abcaccbcaa%22)); // 4%0A//        System.out.println(wf.f(%22a%22,%22aa%22)); // 5%0A    %7D%0A%7D%0A

Solve problem 745