1 class Solution { 2    vector< vector<int> >  pos; 3    vector<string> sen; 4 public: 5  6     vector<string> wordBreak(string s, unordered_set<string> &dict) { 7          getVector(s,dict); 8          string tmp=""; 9          getSentence(s,pos,tmp,0);10         return sen;11     }12    void  getSentence(string s,vector<vector<int> > &pos,string tmp,int start)13     {14 15        for(int i=0;i<pos[start].size();i++)16        if(!pos[start].empty())17        {//cout<<tmp<<endl;18            if(pos[start][i]!=s.size())19             {20 21                 getSentence(s,pos,tmp + s.substr(start,pos[start][i]-start) + " ",pos[start][i]);22             }23             else24            {25            sen.push_back(tmp+s.substr(start,pos[start][i]-start));26 27            }28        }29 30 31 32     }33     void getVector(string s, unordered_set<string> &dict)34     {35 36         int setLen = s.size();37         int start =0;38         pos.resize(setLen);39         for(int i=setLen-1;i>=0;i--)40         {41            if(dict.count(s.substr(i,setLen-i)))42               pos[i].push_back(setLen);43 44         }45         for(int j=setLen-1;j>=0;j--)46         {47             start = 0;48             if(!pos[j].empty())49             for(int k = j;k >0;k--)50                 {51                     if(dict.count(s.substr(start,j-start)))52                         pos[start].push_back(j);53                          start++;54                 }55         }56        57 58 59     }60 61 };