leetcode

0 class Solution {

1 public:

2 int longestStrChain(vector<string> &words) {

3 sort(begin(words), end(words), [](const auto &a, const auto &b) { return a.size() < b.size(); });

4

5 static int dp[1001];

6 memset(dp, 0x00, sizeof(dp));

7

8 int res = 0;

9 for (int i = 0; i < words.size(); i++) {

10 for (int j = i + 1; j < words.size(); j++) {

11 if (words[j].size() == words[i].size()) continue;

12 if (words[j].size() - words[i].size() > 1) break;

13 int k = 0, l = 0, diff = 0;

14 while (k < words[i].size()) {

15 if (words[i][k] == words[j][l])

16 k++, l++;

17 else {

18 l++;

19 if (diff++) break;

20 }

21 }

22 if (diff == 2) continue;

23 res = max(res, dp[j] = max(dp[j], dp[i] + 1));

24 }

25 }

26

27 return res + 1;

28 }

29 };