1
class Solution {
2
 public:
3
  bool wordBreak(string s, vector<string> &wordDict) {
4
    int m = wordDict.size();
5
    int n = s.size();
6
    vector<int> dp(n + 1, 0);
7
    dp[0] = 1;
8
    for (int i = 1; i <= n; i++) {
9
      for (int j = 0; j < m; j++) {
10
        if (i >= wordDict[j].size()) {
11
          for (int k = 0; k < wordDict[j].size(); k++) {
12
            if (s[i - wordDict[j].size() + k] != wordDict[j][k]) goto cnt;
13
          }
14
          if (dp[i - wordDict[j].size()] == 1) dp[i] = 1;
15
          if (dp[n] == 1) return true;
16
        cnt:;
17
        }
18
      }
19
    }
20
    return dp[n];
21
  }
22
};