Leetcode -- Word Break

First try, brutal force, of course TLE

 class Solution {  
 public:  
   bool wordBreak(string s, unordered_set<string> &dict) {  
     return wordBreakHelper(s, 0, dict);  
   }  
   bool wordBreakHelper(const string& s, int start, unordered_set<string>& dict) {  
     if(start >= s.length()) {  
       return true;  
     }  
     for(int i = start; i < s.length(); ++i) {  
       if(dict.count(s.substr(start, i - start + 1)) > 0) {  
         if(wordBreakHelper(s, i + 1, dict)) {  
           return true;  
         }  
       }  
     }  
     return false;  
   }  
 };  

Use dp

 class Solution {  
 public:  
   bool wordBreak(string s, unordered_set<string> &dict) {  
     s = "#" + s;  
     int n = s.length();  
     vector<bool> dp(n, 0);  
     dp[0] = true;  
     for(int i = 1; i < n; ++i) {  
       for(int j = 0; j < i; ++j) {  
         dp[i] = dp[j] && dict.find(s.substr(j+1, i - j)) != dict.end();  
         if(dp[i]) {  
           break;  
         }  
       }  
     }  
     return dp[n - 1];  
   }  
 };