注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

HT·生活

123

 
 
 

日志

 
 

ex140 Word Break II  

2015-05-29 22:52:22|  分类: leetcode |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

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

还是在word break I  ex139的基础上做的,只不过那一题就要判断有一条路径可以分割就行了,所以用一维dp就能保存。而且这里需要把所有的路径都找到,所以dp要开二维,表示i->j是可以分割成为字典里面的单词的。见代码

class Solution {
public:
vector<string> result;
vector<string> wordBreak(string s, unordered_set<string>& wordDict) {
/*
* 网上推荐的都是用的dp规划的算法,不过仔细想想也是
* 先看第一个字符有没有被匹配,然后查看0-1字符是否匹配,然后一直到到s的最后
* 滚动计算结果
*/
unordered_set<string>::iterator it;
string str;
int i, index = 0;
int nsize = s.size();
vector < bool>dp(nsize, false);
vector<vector<bool>> mark(nsize, dp); //mark[i][j]表示 i->j下标的字符串能否分割
for (i = 0; i < nsize; i++)
{
dp[i] = false; //初始化一下

dp[i] = (wordDict.find(s.substr(0, i + 1)) == wordDict.end()) ? false : true;
if (dp[i])
mark[0][i] = true;
//相当于把前面遍历过的在查一遍,看能偶从j+1->i分割
for (int j = 0; j < i; j++)
{
//从j处分割
if (dp[j])
{
//匹配j+1下标开始,总共i-j个字符
bool part = (wordDict.find(s.substr(j + 1, i - j)) == wordDict.end()) ? false : true;
if (part)
{
dp[i] = part;
mark[j + 1][i] = true;
//break;
}
}
}
}
if (!dp[nsize - 1])
return result; //你大爷的 测试集合居然给部分分割的,害的我这里没有判定后面进入死循环了
traverse(mark, s);
return result;
}
void traverse(vector<vector<bool>>mark, string str)
{
int i = 0, j = 0;
int index = 0;
string res;
recursive(mark, str, 0, res); //递归进行深度优先遍历得到结果

}
void recursive(vector<vector<bool>>mark, string str, int start, string res)
{
int i;
int len = mark.size();
if (len == start)
{
if (res[res.size() - 1] == ' ')
res.erase(res.end() - 1);
result.push_back(res);
return;
}
for (i = start; i < len; i++)
{
if (mark[start][i])
{
string tmp = res;
tmp.append(str.substr(start, i - start + 1));
tmp.append(" ");
recursive(mark, str, i + 1, tmp);
}
}
}
};


备用参考
http://www.cnblogs.com/TenosDoIt/p/3385644.html
  评论这张
 
阅读(5)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017