diff options
Diffstat (limited to 'other/longest_string_chain.cpp')
-rw-r--r-- | other/longest_string_chain.cpp | 34 |
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); +} |