(trie,dfs)472. 连接词

472. 连接词

trie+dfs

const int N = 100010;
int son[N][26];
int cnt[N], idx;
bool vis[N];

class Solution {
 public:
  void insert(string &s) {
    int p = 0;
    for (auto c : s) {
      int u = c - 'a';  // 确定分支
      if (!son[p][u]) son[p][u] = ++idx;
      p = son[p][u];
    }
    cnt[p] = 1;
  }
  bool query(string &s, int cur) {
    int p = 0;
    if (cur == s.size()) return true;
    if (vis[cur]) return false;
    for (int i = cur; i < s.size(); i++) {
      int u = s[i] - 'a';
      if (!son[p][u]) break;
      p = son[p][u];
      if (cnt[p]) {
        if (query(s, i + 1)) return true;
      }
    }
    vis[cur] = true;
    return false;
  }
  vector<string> findAllConcatenatedWordsInADict(vector<string> &words) {
    sort(words.begin(), words.end(),
         [](const string &a, const string &b) { return a.size() < b.size(); });
    memset(son, 0, sizeof son), memset(cnt, 0, sizeof cnt),
        memset(vis, 0, sizeof vis);
    idx = 0;

    vector<string> res;
    for (auto &s : words) {
      if (s.empty()) continue;
      if (query(s, 0)) res.push_back(s);
      insert(s);
      memset(vis, 0, sizeof vis);
    }

    return res;
  }
};