Given a string s and a dictionary of words dict, add spaces in s to construct a sentence where each word is a valid dictionary word.

Return all such possible sentences.

For example, given

s = "catsanddog",

dict = ["cat", "cats", "and", "sand", "dog"].

A solution is ["cats and dog", "cat sand dog"].

PS:use DFS to solve the follow up question

1 #include 
     
        2 #include 
      
         3 #include 
       
          4 #include 
        
           5 #include 
         
            6   7 using namespace std;  8   9 set
          
            myset; 10 vector
           
             vstring; 11 bool ** pmatrix = NULL; 12 string strtomatch; 13 14 template
            
              15 void BuildMatrix(T *** pmaze,unsigned row_num,unsigned column_num) 16 { 17 *pmaze = new T*[row_num]; 18 for(unsigned i=0;i
             
               24 void ReleaseMatrix(T ***pmaze,unsigned row_num) 25 { 26 if(!pmaze) return; 27 28 for(unsigned i=0;i
              
               =length) return; 37 unsigned originallength = 0; 38 for(i=++j;j
               
                >dicwordnum; 59 60 for(int i=0;i
                
                 >strtomatch; 62 myset.insert(strtomatch); 63 } 64 65 cin>>strtomatch; 66 unsigned strlength = strtomatch.length(); 67 68 BuildMatrix(&pmatrix,strlength,strlength); 69 70 for(int i=0;i
                 
                  =0;--i){ 87 bool isallfalse = true; 88 for(int j = i;j
                  
                   =0)){ 96 for(int j = 0;j
                   
                    ::iterator iter = vstring.begin();iter!=vstring.end();++iter){107 cout<<*iter<
                    
                     >case_num;120 121 for(int i=0;i
                    
                   
                  
                 
                
               
              
             
            
           
          
         
        
       
      
     

txtII.in

35cat cats and sand dog catsanddog7abc ab de cde abcd e abcde abcde2a b ab

txtII.out

Case 1: cat  sand  dog cats  and  dog Case 2: ab  cde abc  de abcd  e abcde Case 3: a  b

//深度遍历矩阵，用递归解决问题