leetcode

Solution to some Leetcode problems written in C++

git clone git://git.dimitrijedobrota.com/leetcode.git

1048.cpp (987B)

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 };