LeetCode--Wrod Break

---恢复内容开始---

 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             else
15             {
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 };

递归到Dp转化的经典题目

递归如下

 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 };

---恢复内容结束---