139. 单词拆分

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