leetcode 1048 - Longest String Chain

https://leetcode.com/problems/longest-string-chain/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
public:
int longestStrChain(vector<string>& words) {
auto mycomp = [](const string &s1, const string &s2) {
return s1.size() < s2.size();
};

sort(words.begin(), words.end(), mycomp);

unordered_map<string, int> count;
int longest = 0;

for (auto &word : words) {
string tmp;
int ans = 1;
for (int i = 0; i < word.size(); i++) {
tmp = word.substr(0, i) + word.substr(i+1);
ans = max(ans, count[tmp] + 1);
}
count[word] = ans;
longest = max(longest, ans);
}

return longest;
}
};