首页 > 代码库 > [LeetCode] Word Break II

[LeetCode] Word Break II

2024-07-08 12:30:36   225人阅读

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"].

以下时间复杂度过高，没有通过的：

void word_Merge(vector<string> &result,  string s0,int newBegin,  int len,   map<pair<int,int>,string> m)
                 //result存放结果，s0是result存放的值，newBegin是下一个subString开始的下标                                                                       {    map<pair<int,int>,string>::iterator iter1;    if(newBegin == len)        result.push_back(s0);    else    {       for(iter1 = m.begin(); iter1 != m.end(); iter1++)       {           string newS = s0;           if((*iter1).first.first == newBegin)           {               newS += (*iter1).second;               if((*iter1).first.second != len-1)                   newS += " ";                word_Merge(result,newS,(*iter1).first.second+1,len,m);           }//end if       }//end for    }//end if else}//end word_Mergeclass Solution {public:vector<string> wordBreak(string s, unordered_set<string> &dict) {          map<pair<int,int>,string> m;  //m中存放的是每个子字符串以及对应的开始结束位置<int,int>;            for(string::size_type i=0;i<s.size();i++){          for(string::size_type j=i;j<s.size();j++){            string str = s.substr(i,j-i+1);            if(dict.find(str) != dict.end()){                m.insert( make_pair( make_pair(i,j),str) );            }//end if          }//end for      }//end for      vector<string> result;      int len = s.size();      for(map<pair<int,int>,string>::iterator iter=m.begin();iter!=m.end();iter++){                      if((*iter).first.first == 0){              string S0 = (*iter).second;              if((*iter).first.second != len-1)                  S0 += " ";               word_Merge(result,S0,(*iter).first.second+1,len,m);          }//end if                }//end for   return result;}//end wordBreak};

没有用动态规划（dynamic programming），进行很多的递归调用。虽然函数功能没有问题，但通不过很正常。

下面看使用动态规划的方法：

void collect(vector<vector<int>>& mark, int ind, const string& s, string path, vector<string>& result){             //ind是s中子字符串开始的下标，mark里第ind项存放子字符串结束的下标+1即stop。
        for(int i=0;i<mark[ind].size();i++){            int stop = mark[ind][i];            string sub=s.substr(ind,stop-ind);            string newpath=path+(ind==0?sub:" "+sub);   ////此句写的很简洁            if(stop==s.length())                result.push_back(newpath);            else                collect(mark,stop,s,newpath,result);    }//end for}//end collectvector<string> wordBreak(string s, unordered_set<string> &dict) {    vector<vector<int>> mark(s.length(),vector<int>());    for(int stop=s.length();stop>=0;stop--){    //用两个for循环给mark赋值，中间用了if...continue..大大节省了时间        if(stop<s.length() && mark[stop].empty())continue;//本句最节省时间！！！//如果没有以下标stop开始的字符串，就不必有下面for循环中以stop-1结束的字符串了，所以continue        for(int start=stop-1;start>=0;start--)//以下标start开始，stop结束的字符串，即s中[start,stop)之间;            if(dict.count(s.substr(start,stop-start)))                mark[start].push_back(stop);    }//end for    vector<string> result;    collect(mark,0,s,"",result);    return result;}//end wordBreak

其中vector<vector<int>> mark，mark中每一项是一个vector，比如题目中的例子s=“catsanddog”，

则mark中的第0项存储的（4，3），即可以从s取两个字符子字符串下标是[0,4)即“cats” 和 [0,3)即“cat”。

这个与我上面的m有异曲同工之妙，只不过m的类型是

map<pair<int,int>,string>类型，把下标和子字符串都一项项记录进去了，太麻烦了！

 

总结：

（1）数据类型的使用很重要

（2）由于使用合适的数据类型vector<vector<int>>才能方便的用if...continue省略很多for循环不必要的执行。

       用第一个程序中的map<pair<int,int>,string>类型比较难有这样的设计。

 


联系
我们