aboutsummaryrefslogtreecommitdiff
path: root/other/longest_string_chain.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'other/longest_string_chain.cpp')
-rw-r--r--other/longest_string_chain.cpp34
1 files changed, 34 insertions, 0 deletions
diff --git a/other/longest_string_chain.cpp b/other/longest_string_chain.cpp
new file mode 100644
index 0000000..afa805c
--- /dev/null
+++ b/other/longest_string_chain.cpp
@@ -0,0 +1,34 @@
+#include "leetcode.h"
+
+class Solution {
+public:
+ int longestStrChain(vector<string> &words) {
+ vector<unordered_set<string>> vus(17);
+ for (auto i : words)
+ vus[i.size()].insert(i);
+ unordered_map<string, int> um;
+ int ans = 1;
+ for (int i = 16; i; i--) {
+ if (vus[i - 1].empty())
+ continue;
+ for (auto j : vus[i]) {
+ int wVal = um[j] ? um[j] : 1;
+ for (int k = 0; k < j.size(); k++) {
+ string prev = j.substr(0, k) + j.substr(k + 1);
+ int pVal = um[prev] ? um[prev] : 1;
+ if (vus[i - 1].find(prev) != vus[i - 1].end() && wVal >= pVal) {
+ um[prev] = wVal + 1;
+ ans = max(ans, wVal + 1);
+ }
+ }
+ }
+ }
+ return ans;
+ }
+};
+
+int main() {
+ Solution obj;
+ vector<string> words = {"a", "b", "ba", "bca", "bda", "bdca"};
+ cout << obj.longestStrChain(words);
+}