Concatenated Words LeetCode solution in C++

1
class Solution {
2
 public:
3
  int checkForConcatenation(unordered_set<string> &st, string w, int i, vector<int> &dp) {
4
    if (i == w.size()) return 1;
5
    if (dp[i] != -1) return dp[i];
6
    for (int j = i; j < w.size(); ++j) {
7
      string t = w.substr(i, j - i + 1);
8
      if (t.size() != w.size() && st.find(t) != st.end()) {
9
        if (checkForConcatenation(st, w, j + 1, dp)) return dp[i] = 1;
10
      }
11
    }
12
    return dp[i] = 0;
13
  }
14

15
  vector<string> findAllConcatenatedWordsInADict(vector<string> &words) {
16
    vector<string> ans;
17
    unordered_set<string> st;
18
    for (auto w : words) st.insert(w);
19
    for (auto w : words) {
20
      vector<int> dp(w.size(), -1);
21
      if (checkForConcatenation(st, w, 0, dp)) ans.push_back(w);
22
    }
23
    return ans;
24
  }
25
};