1 class Solution { 2 public: 3     bool wordBreak(string s, unordered_set<string> &dict) { 4         int nsize=s.size(); 5         int i=0,j=0; 6         bool *dp = new bool[nsize]; 7         memset(dp,false,sizeof(dp)); 8          9         for(i=0;i<nsize;++i)10         {11             dp[i] = ((dict.find(s.substr(0,i+1))!=dict.end())?true:false);12             if(dp[i])13                 continue;14             else15             {16                 for(j=0;j<i;++j)17                 {18                     if(dp[j])19                     {20                         dp[i] = ((dict.find(s.substr(j+1,i-j))!=dict.end())?true:false) | dp[i];21                     }22                 }23             }24         }25         return dp[nsize-1];26         delete []dp;27     }28 };

 1 class Solution { 2 public: 3     bool wordBreak(string s, unordered_set<string> &dict) { 4         if(s.length() == 0) 5         { 6             return false; 7         } 8         for(int i = 1 ; i <= s.length() ; ++i) 9         {10             string word = s.substr(0,i);11             string str = s.substr(i,s.length()-i);12             if(dict.find(word) != dict.end() && wordBreak(str,dict))13             {14                 return true;15             }16         }17         return false;18     }19 };