Longest String Chain LeetCode solution in C++

1
class Solution {
2
  int dfs(unordered_map<string, int> &m, unordered_set<string> &setWords, const string &w) {
3
    if (m.count(w)) return m[w];
4
    int maxLen = 1;
5

6
    for (int i = 0; i < w.size(); ++i) {
7
      auto preWord = w.substr(0, i) + w.substr(i + 1);
8
      if (setWords.count(preWord)) {
9
        int newLen = 1 + dfs(m, setWords, preWord);
10
        maxLen = max(newLen, maxLen);
11
      }
12
    }
13
    m[w] = maxLen;
14
    return maxLen;
15
  }
16

17
 public:
18
  int longestStrChain(vector<string> &words) {
19
    unordered_map<string, int> m;
20
    unordered_set<string> setWords(words.begin(), words.end());
21
    int res = 0;
22

23
    for (auto &w : words) {
24
      res = max(res, dfs(m, setWords, w));
25
    }
26
    return res;
27
  }
28
};