Word Break II

参考http://www.cnblogs.com/TenosDoIt/p/3385644.html#commentform
  1 #include <iostream>
  2 #include <unordered_set>
  3 #include <string>
  4 #include <array>
  5 
  6 using namespace std;
  7 
  8 class Solution {
  9 public:
 10     vector<string> wordBreak(string s, unordered_set<string> &dict)
 11     {
 12         // Note: The Solution object is instantiated only once and is reused by each test case.
 13         vector<string> result;
 14         if(dict.empty())
 15             return result;
 16         if (s.empty())
 17         {
 18             return result;
 19         }
 20         const int len = s.size();
 21         bool *canBreak = new bool [len]; //canBreak[i] = true 表示s[0~i]是否能break
 22         memset(canBreak, 0, sizeof(bool)*len);
 23         bool **pre = new bool *[len];//如果s[k..i]是字典中的单词,则pre[i][k]=true
 24         for(int i = 0; i < len; i++)
 25         {
 26             pre[i] = new bool[len];
 27             memset(pre[i], 0 , sizeof(bool)*len);
 28         }
 29 
 30         for(int i = 1; i <= len; i++)
 31         {
 32             if(dictContain(dict, s.substr(0, i)))
 33             {
 34                 canBreak[i-1] = true;
 35                 pre[i-1][0] = true;
 36             }
 37             if(canBreak[i-1] == true)
 38             {
 39                 for(int j = 1; j <= len - i; j++)
 40                 {
 41                     if(dictContain(dict,s.substr(i, j)))
 42                     {
 43                         canBreak[j+i-1] = true;
 44                         pre[j+i-1][i] = true;
 45                     }
 46                 }
 47             }
 48         }
 49         //return false;
 50         vector<int> insertPos;
 51         getResult(s, pre, len, len-1, insertPos, result);
 52         return result;
 53     }
 54 
 55     bool dictContain(unordered_set<string> &dict, string s)
 56     {
 57         unordered_set<string>::iterator ite = dict.find(s);
 58         if(ite != dict.end())
 59             return true;
 60         else return false;
 61     }
 62 
 63     //在字符串的某些位置插入空格，返回新字符串
 64     string insertBlank(string s,vector<int>pos)
 65     {
 66         string result = "";
 67         int base = 0;
 68         for(int i = pos.size()-1; i>=0; i--)
 69         {
 70             if(pos[i] == 0)continue;//开始位置不用插入空格
 71             result += (s.substr(base, pos[i]-base) + " ");
 72             base = pos[i];
 73         }
 74         result += s.substr(base, s.length()-base);
 75         return result;
 76     }
 77 
 78     //从前驱路径中构造结果
 79     void getResult(string s, bool **pre, int len, int currentPos,
 80         vector<int>insertPos,
 81         vector<string> &result)
 82     {
 83         if(currentPos == -1)
 84         {
 85             result.push_back(insertBlank(s,insertPos));
 86             //cout<<insertBlank(s,insertPos)<<endl;
 87             return;
 88         }
 89         for(int i = 0; i <= currentPos; i++)
 90         {
 91             if(pre[currentPos][i] == true)
 92             {
 93                 insertPos.push_back(i);
 94                 getResult(s, pre, len, i-1, insertPos, result);
 95                 insertPos.pop_back();
 96             }
 97         }
 98     }
 99 };
100 
101 int main(){
102     string s = "catsanddog";
103     unordered_set<string> dict;
104     array<string, 5> myarray = {"cat", "cats", "and", "sand", "dog"};
105     dict.insert(myarray.begin(), myarray.end());
106     Solution sln;
107     //cout << sln.wordBreak(s, dict) << endl;    
108 
109     vector<string> ret = sln.wordBreak(s,dict);
110     for (vector<string>::iterator iter = ret.begin(); iter != ret.end(); iter++)
111     {
112         cout << *iter << endl;
113     }
114     
115 }