DP

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;
  void Build(vector<string> &wordDict) {
    for (auto &str : wordDict) {
      reverse(str.begin(), str.end());
      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 >= 0 && 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;
    auto nexts_index = match(s, index);
    //one_dim_print(nexts_index);
    for (auto r = nexts_index.rbegin(); r < nexts_index.rend(); r++) {

      DFS(s, *r);
    }
  }
  bool wordBreak(string s, vector<string> &wordDict) {
    trie = new Node;
    Build(wordDict);
    vector<bool> dp(s.size(), false);
    for (int i = 0; i < s.size(); i++) {
      auto v = match(s, i);
      for (auto &vv : v) {
        if (vv == -1 || dp[vv]) {
          dp[i] = true;
          break;
        }
      }
    }
    return dp[s.size() - 1];
  }
};