首页 > 代码库 > [LeetCode]Word Break
[LeetCode]Word Break
题目：Word Break
将给定的字符串按照给定的单词表拆分开，判断是否能在给定的单词表中拆分该字符串
单词表中单词不重复，但是可以在字符串中重复出现。
思路：
暴力搜索，只要遍历单词表每次找到与字符串的当前位置往后的n(单词表中当前遍历到的单词长度)的字符重合则表示可以拆分。
这种方法，时间复杂度很高，无法通过。后面还会介绍，代码先略过。
思路：BFS（广度优先搜索）
每次搜索能与当前位置后面n(n是匹配的单词的长度，是可变的)个字符匹配的所有单词，加入队列中，然后修改当前的位置，同时，当前的元素出队；
知道找一个单词使得当前位置修改后到达给定字符串的尾部。
例如：
s = "leetcode" worDict = {"leet","code"} pos = 0->n(8);
初始状态，当pos = 0时，leet与[0,4]的字符匹配，每次需要知道之后pos开始的位置和当前匹配的单词在单词表中的位置，因此我用pair记录上面两个值，将他们入队；
Q = {<0,4>}
然后单词表中没有其他单词匹配，修改当前位置pos = Q.front().second；
修改后的pos < s.size()；则继续匹配单词表，如此循环；
Q = {<0,4>，<1,8>}，此时，找到一个组合，由于只需要判断是否有这样的组合，所有直接返回。
/**广度优先搜索**/ bool LeetCode::wordBreakBFS(string s, vector<string>& wordDict){ if (!wordDict.size())return false; queue<pair<int, int>>Q;//first是单词在词典中的下标，second是当前单词之后开始的位置 auto it = wordDict.cbegin(); while (it != wordDict.cend()){ if ((*it).size() <= s.size() && !s.substr(0, (*it).size()).compare(*it)){//字符串与s的开始部分匹配，找到开始的字符串 if ((*it).size() == s.size())return true;//和一个单词完全匹配 Q.push(make_pair(it - wordDict.cbegin(),(*it).size())); } ++it; } while (!Q.empty()){ auto p = Q.front(); Q.pop(); auto it = wordDict.cbegin(); while (it != wordDict.cend()){//遍历完单词表，找到所有的可能 if ((*it).size() + p.second <= s.size() && !s.substr(p.second, (*it).size()).compare(*it)){//字符串与s的从p.second开始部分匹配 if (p.second + (*it).size() == s.size())return true;//匹配完毕 Q.push(make_pair(it - wordDict.cbegin(), p.second + (*it).size())); } ++it; } } return false; }
但是，上面的方法还是不能通过，超时了，因为给的是vector在找匹配单词上耗时与爆搜是一样的，而且，没有办法减少重复的搜索，所以效率和爆搜差不多，可能是我没有想到什么好的办法减少重复搜索，请知道的人指导一下，总之我没有用这个思路通过。
思路：
考虑到不需要找到具体的路劲，我在想动态规划是不是可以呢？
其实是可以的，F(n)表示s字符串中0到n个字符是否能用单词表的单词表示；
F(n) = F(k) && (s.substr(k,n) in wordDict);存在 k in [0 - n]
上面表达式的意思：存在这样的k属于[0,n）使得 F(n) = F(k) 且 (s中k到n的子串在单词表中能找到单词与它匹配)
所以，可以从零开始找到字符串每个位置的对应的F(k)值，然后，返回F(s.size())即可。
注意：
vector<bool>flag表示的F()，它的大小应该是s.size()+1；
每次求end对应位置的F(end)值，需要遍历[0,end)的所有值中是否又满足上面的k（start）
/** 动态规划：F(n) = F(k) && (s.substr(k,n) in wordDict);存在 k in [0 - n] **/ bool LeetCode::wordBreakBF(string s, vector<string>& wordDict){ if (!wordDict.size())return false; sort(wordDict.begin(), wordDict.end()); vector<bool> flag(s.size() + 1,false);//标记每个地方对应的字符串是否能被拼凑出来 flag.at(0) = true; for (int end = 1; end <= s.size(); end++){ for (int start = end - 1; start >= 0; start--){//检查是否存在上面的k，拼凑出[0,end]的字符串 if (flag.at(start)){ string temp = s.substr(start,end - start);//获得从start到end的子串 auto it = wordDict.begin(); while (it != wordDict.end()){//遍历单词表 auto r = temp.compare(*it); if (!r){ flag.at(end) = true; break; } else if(r < 0){//单词表已排序 break; } ++it; } } } } return flag.at(s.size()); }
题目：Word BreakII
在上面的基础上要找出所有可能的不同组合。
单词表中单词不重复，但是可以在字符串中重复出现。
基本上上面的3种方法都可以在这个问题上使用；
思路：
暴力搜索：
定义一个数组记录搜索的路径，同时找到方便回溯时的开始位置，暴力搜索和深度优先很相似；
先找一个可能匹配整个字符串的数组，然后一直匹配到最后，如果不能完全匹配就回溯，此时，要从记录的path的值为起始遍历整个字典。
/** 暴力搜索 Time Limit Exceeded **/ vector<string> LeetCode::wordBreak2(string s, vector<string>& wordDict){ vector<string> retStrs; if (!wordDict.size())return retStrs; int i = 0, pos = 0; vector<int> path; while (pos < s.size()){ for (; i < wordDict.size(); i++){//找到匹配的单词 string& temp = wordDict.at(i); //单词长度不超过剩下的未匹配长度 if (pos + temp.size() <= s.size() && !s.compare(pos, temp.size(), temp)){//temp.compare(s.substr(pos,temp.size())) pos += temp.size(); path.push_back(i); i = 0; break; } } if (pos == s.size()){//s完全匹配成功 auto it = path.cbegin(); string s; while (it != path.cend()){ s.append(wordDict.at(*it)); ++it; if(it != path.cend())s.append(" "); } retStrs.push_back(s); i = wordDict.size(); } if (i == wordDict.size()){//匹配不成功，回溯 if (!path.size())break;//回溯到开始时，还是没有匹配，则跳出循环 i = path.at(path.size() - 1);//不能用back()，他返回的是引用 pos -= wordDict.at(i).size(); path.pop_back(); ++i; } } return retStrs; }
结果超时了。在和前面第一个问题差不多的一个测试用例的地方超时；
思路：BSF
过程和前面差不多，只是，在判断成功的地方合并字符串，而不是返回；同时为了能找回路，需要有辅助数组来记住队列弹出的元素。
同时还要记住后面的元素是因为前面的哪个元素而入队的，即入队的路径。这里不再贴代码。
同样要面对暴力搜索时的超时测试用例。
思路：动态规划
直接在上面动态规划的思想上来修改，即是，在搜索的时候记录下匹配的路径。
我的做法是：定义一个record数组vector<vector<pair<int,int>>>数组的一维的大小和flag相同，他分别对应flag的每个值，
F(n) = F(k) && (s.substr(k,n) in wordDict);存在 k in [0 - n]；k可能有多个值；
record的二维的大小是该位置pos对应的s的子串s.substr(0,pos)匹配的多个组合中的k的值和子串对应的单词表的位置;
first记录flag为true时的单词表的下标,second记录flag为true时的上一个依赖的位置。
于是可通过下面的语句记录路径
record.at(end).push_back(make_pair(it - wordDict.begin(),start));
然后getAllPathFromWB()函数来得到最终的字符串的组合。
该函数getAllPathFromWB()中定义visited数组记录record二维数组中第二维的起始位置，以便回溯的时候从前面的位置接着向后面遍历。
注意：
1.循环是从record的尾部即字符串s的尾部开始的，且该位置没有对应visited的值，因为，它是外循环，不需要记录上一次的遍历的位置。
2.找到一个完整的组合后，删除栈顶元素，并将visited数组的尾部元素加一
3.整个getAllPathFromWB()的思想类似于深度遍历。
void LeetCode::getAllPathFromWB(vector<string>& wordDict, vector<string>& strs, vector<vector<pair<int, int>>>& record){ stack<pair<int,int>>s; vector<int>visited; int i = record.size() - 1; auto it = record.at(i).cbegin(); while (it != record.at(i).cend()){//record的最后元素开始根据记录的下标回溯 s.push((*it)); while (!s.empty()){ auto p = s.top(); if (!p.second){//一条完整路径 vector<pair<int,int>>temp; string str; while (!s.empty()){//出栈并组合单词为句子 auto t = s.top(); s.pop(); str.append(wordDict.at(t.first)); temp.push_back(t); if (!s.empty())str.append(" "); } strs.push_back(str); for (int j = temp.size() - 1; j > 0 ; --j){//入栈，但是去掉栈顶元素(j > 0) s.push(temp.at(j)); } if (visited.size() > 0)++visited.back();//记录最后一个单词的上一个位置的数组加一 } else{ int j = 0; if (visited.size() && visited.size() == s.size()){//visited数组已经存在 j = visited.back(); if (j == record.at(p.second).size()){//record的当前数组是否遍历完 visited.pop_back(); if(visited.size() > 0)++visited.back();//可能回溯到最上面一个句子 s.pop(); continue; } s.push(record.at(p.second).at(j)); } else{//visited数组不存在 s.push(record.at(p.second).at(j)); visited.push_back(j); } } } ++it; } } /** 动态规划：F(n) = F(k) & s.substr(k,n) in wordDict;存在 k in [0 - n] **/ vector<string> LeetCode::wordBreak2BF(string s, vector<string>& wordDict){ vector<string> retStrs; if (!wordDict.size())return retStrs; sort(wordDict.begin(), wordDict.end()); vector<bool> flag(s.size() + 1, false);//标记每个地方对应的字符串是否能被拼凑出来 vector<vector<pair<int,int>>> record(s.size() + 1);//first记录flag为true时的单词表的下标,second记录flag为true时的上一个依赖的位置 flag.at(0) = true; for (int end = 1; end <= s.size(); end++){ for (int start = end - 1; start >= 0; start--){//检查是否存在上面的k，拼凑出[0,end]的字符串 if (flag.at(start)){ string temp = s.substr(start, end - start);//获得从start到end的子串 auto it = wordDict.begin(); while (it != wordDict.end()){//遍历单词表 auto r = temp.compare(*it); if (!r){ flag.at(end) = true; record.at(end).push_back(make_pair(it - wordDict.begin(),start)); break; } else if (r < 0){//单词表已排序 break; } ++it; } } } } if (flag.at(s.size())){ getAllPathFromWB(wordDict,retStrs,record); } return retStrs; }
[LeetCode]Word Break