0745 solved.

liuyubobobo · liuyubobobo · commit 96fed65f09f8 · 2022-07-14T01:36:27.000-07:00
diff --git a/0501-1000/0745-Prefix-and-Suffix-Search/cpp-0745/CMakeLists.txt b/0501-1000/0745-Prefix-and-Suffix-Search/cpp-0745/CMakeLists.txt
@@ -0,0 +1,6 @@
+cmake_minimum_required(VERSION 3.22)
+project(cpp_0745)
+
+set(CMAKE_CXX_STANDARD 14)
+
+add_executable(cpp_0745 main.cpp)
diff --git a/0501-1000/0745-Prefix-and-Suffix-Search/cpp-0745/main.cpp b/0501-1000/0745-Prefix-and-Suffix-Search/cpp-0745/main.cpp
@@ -0,0 +1,86 @@
+/// Source : https://leetcode.com/problems/prefix-and-suffix-search/
+/// Author : liuyubobobo
+/// Time   : 2022-07-14
+
+#include <iostream>
+#include <vector>
+#include <algorithm>
+#include <map>
+
+using namespace std;
+
+
+/// Suffix + Prefix
+/// Time Complexity: init: O(sum_of_characters)
+///                  query: O(|prefix| + |suffix|)
+/// Space Complexity: O(sum_of_characters)
+class Trie {
+
+private:
+    struct Node{
+        map<char, Node*> next;
+        int index = -1;
+    };
+    Node* root;
+
+public:
+    Trie(){
+        root = new Node();
+    }
+
+    /** Inserts a word into the trie. */
+    void insert(const string& word, int index){
+
+        Node* cur = root;
+        bool flag = false;
+        for(char c: word){
+            if(cur->next.find(c) == cur->next.end()){
+                cur->next[c] = new Node();
+            }
+            cur = cur->next[c];
+
+            if(c == '#') flag = true;
+            if(flag) cur->index = index;
+        }
+    }
+
+    int get(const string& s) {
+
+        Node* cur = root;
+        for(char c: s){
+            if(cur->next.find(c) == cur->next.end())
+                return -1;
+
+            cur = cur->next[c];
+        }
+        return cur->index;
+    }
+};
+
+class WordFilter {
+
+private:
+    Trie trie;
+
+public:
+    WordFilter(vector<string> words) {
+        for(int i = 0 ; i < words.size() ; i ++){
+            string s = words[i];
+            for(int j = s.size() - 1; j >= 0; j --){
+                string suf = s.substr(j);
+                trie.insert(suf + "#" + s, i);
+            }
+        }
+
+    }
+
+    int f(string prefix, string suffix) {
+        return trie.get(suffix + "#" + prefix);
+    }
+};
+
+
+int main() {
+
+    return 0;
+}
diff --git a/readme.md b/readme.md
@@ -750,6 +750,7 @@ email: [liuyubobobo@gmail.com](mailto:liuyubobobo@gmail.com)
 | 740 | [Delete and Earn](https://leetcode.com/problems/delete-and-earn/description/) | [solution](https://leetcode.com/problems/delete-and-earn/solution/) | [C++](0501-1000/0740-Delete-and-Earn/cpp-0740/) | | |
 | 741 | [Cherry Pickup](https://leetcode.com/problems/cherry-pickup/description/) | [solution](https://leetcode.com/problems/cherry-pickup/solution/)<br/>[缺：自底向上的动态规划] | [C++](0501-1000/0741-Cherry-Pickup/cpp-0741/) | | |
 | | | | | | |
+| 745 | [Prefix and Suffix Search](https://leetcode.com/problems/prefix-and-suffix-search/) | [solution](https://leetcode.com/problems/prefix-and-suffix-search/solution/) | [C++](0501-1000/0745-Prefix-and-Suffix-Search/cpp-0745/) | | |
 | 746 | [Min Cost Climbing Stairs](https://leetcode.com/problems/min-cost-climbing-stairs/) | [solution](https://leetcode.com/problems/min-cost-climbing-stairs/solution/) | [C++](0501-1000/0746-Min-Cost-Climbing-Stairs/cpp-0746/) | | |
 | 747 | [Largest Number At Least Twice of Others](https://leetcode.com/problems/largest-number-at-least-twice-of-others/description/) | [solution](https://leetcode.com/problems/largest-number-at-least-twice-of-others/solution/) | [C++](0501-1000/0747-Largest-Number-At-Least-Twice-of-Others/cpp-0747/) | | |
 | | | | | | |
