DFS

struct Node {
  Node *next[30];
  bool word_end;
  Node() {
    memset(next, 0, sizeof(next));
    word_end = false;
  }
};

class Solution {
public:
  Node *trie;
  bool global_check = false;
  vector<bool>vis;
  void Build(vector<string> &wordDict) {
    for (const auto &str : wordDict) {
      Node *p = trie;
      for (const auto &c : str) {
        if (p->next[c - 'a'] == nullptr) {
          p->next[c - 'a'] = new Node;
        }
        p = p->next[c - 'a'];
      }
      p->word_end = true;
    }
  }
  vector<int> match(const string &s, int index) {
    vector<int> res;
    Node *p = trie;
    while (index < s.length() && p != nullptr) {
      if (p->next[s[index] - 'a']) {
        p = p->next[s[index] - 'a'];
        index++;

        if (p->word_end) {
          res.push_back(index);
        }
      } else
        break;
    }
    return res;
  }
  void DFS(const string &s, int index) {
    if (index == s.length()) {
      global_check = true;
      return;
    }
    if (global_check)
      return;
    if(vis[index])return;
    vis[index] = true;
    auto nexts_index = match(s, index);
    for (const auto &i : nexts_index) {
      DFS(s, i);
    }
  }
  bool wordBreak(string s, vector<string> &wordDict) {
    trie = new Node;
    Build(wordDict);
    vis = vector<bool>(s.size()+1, false);
    DFS(s,0);
    return global_check;
  }
};