0745 new algo added.

liuyubobobo · liuyubobobo · commit 0e5154c92ee5 · 2022-07-14T11:43:40.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
@@ -3,4 +3,4 @@ project(cpp_0745)
 
 set(CMAKE_CXX_STANDARD 14)
 
-add_executable(cpp_0745 main.cpp)
+add_executable(cpp_0745 main2.cpp)
diff --git a/0501-1000/0745-Prefix-and-Suffix-Search/cpp-0745/main2.cpp b/0501-1000/0745-Prefix-and-Suffix-Search/cpp-0745/main2.cpp
@@ -0,0 +1,64 @@
+/// 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;
+
+
+/// Using Hash + Map
+/// Time Complexity: init: O(|words| * len^2)
+///                  query: O(|prefix| + |suffix|)
+/// Space Complexity: O(|words| * len^2)
+class WordFilter {
+
+private:
+    map<pair<long long, long long>, int> table;
+
+public:
+    WordFilter(vector<string> words) {
+
+        for(int i = 0 ; i < words.size() ; i ++)
+            insert(words[i], i);
+
+    }
+
+    int f(string prefix, string suffix) {
+
+        long long pre_hash = 0;
+        for(int i = 0; i < prefix.size(); i ++)
+            pre_hash = pre_hash * 27 + (prefix[i] - 'a' + 1);
+
+        long long suf_hash = 0;
+        for(int i = suffix.size() - 1; i >= 0; i --)
+            suf_hash = suf_hash * 27 + (suffix[i] - 'a' + 1);
+
+        auto iter = table.find({pre_hash, suf_hash});
+        return iter == table.end() ? -1 : iter->second;
+    }
+
+private:
+    void insert(const string& s, int index){
+
+        long long pre_hash = 0;
+        for(int i = 0; i < s.size(); i ++){
+            pre_hash = pre_hash * 27 + (s[i] - 'a' + 1);
+
+            long long suf_hash = 0;
+            for(int i = s.size() - 1; i >= 0; i --){
+                suf_hash = suf_hash * 27 + (s[i] - 'a' + 1);
+                table[{pre_hash, suf_hash}] = index;
+            }
+        }
+    }
+};
+
+
+int main() {
+
+    return 0;
+}

Original file line number	Diff line number	Diff line change
`@@ -3,4 +3,4 @@ project(cpp_0745)`
`3`	`3`
`4`	`4`	`set(CMAKE_CXX_STANDARD 14)`
`5`	`5`
`6`		`-add_executable(cpp_0745 main.cpp)`
	`6`	`+add_executable(cpp_0745 main2.cpp)`