leetcode

Solution to some Leetcode problems written in C++
git clone git://git.dimitrijedobrota.com/leetcode.git
Log | Files | Refs | README | LICENSE

1048.cpp (987B)

      1 class Solution {
      2   public:
      3     int longestStrChain(vector<string> &words) {
      4         sort(begin(words), end(words), [](const auto &a, const auto &b) { return a.size() < b.size(); });
      5 
      6         static int dp[1001];
      7         memset(dp, 0x00, sizeof(dp));
      8 
      9         int res = 0;
     10         for (int i = 0; i < words.size(); i++) {
     11             for (int j = i + 1; j < words.size(); j++) {
     12                 if (words[j].size() == words[i].size()) continue;
     13                 if (words[j].size() - words[i].size() > 1) break;
     14                 int k = 0, l = 0, diff = 0;
     15                 while (k < words[i].size()) {
     16                     if (words[i][k] == words[j][l])
     17                         k++, l++;
     18                     else {
     19                         l++;
     20                         if (diff++) break;
     21                     }
     22                 }
     23                 if (diff == 2) continue;
     24                 res = max(res, dp[j] = max(dp[j], dp[i] + 1));
     25             }
     26         }
     27 
     28         return res + 1;
     29     }
     30 };