单词分割
例如，给定：
s = “leetcode”,
dict = ["leet", "code"].
则结果为真，因为字符串S可以分割为leet 和code两个合法单词。
1.普通方法
[htML]
bool WordbreakHelPEr(string& str, setstring> & dict, int nStart)
{
if (nStart == str.length())
{
return true;
}
for (setstring> ::ITerator iter=dict.begin(); iter != dict.end(); iter++)
{
int nLen = (*iter).length();
int nEnd = nStart + nLen;
if (nEnd > str.length())
{
//单词太长直接超过了str字符串剩余部分长度。因此不可能在字符串Str中
continue;
}
if(str.substr(nStart,nLen) == *iter)
{
if (WordBreakHelper(str, dict, nStart+nLen))
{
return true; //想一想为什么这么递归
}
}
}
return false;
}
时间负责度是O(n^2)。
2.动态规划的方法
用动态规划的方法来解决单词分割的关键是：
1、定义一个数组t[],t[i]==true代表字符串的前i个字符是可以用给定字典分割的。
2、数组的初始状态为t[0]==true。
[html]
bool WordBreak(string& str, setstring> & dict)
{
bool *bAry = new bool[str.length()+1]; //想一想为什么要加1
memset(bAry,false,str.length()+1);
bAry[0] = true;
for (int i=0; istr.length(); i++)
{
if (!bAry[i])
{
continue;
}
//想一想为什么要在以i代表的位置为立足点对所有可能的单词进行扫描（这很必要）
for (setstring> ::iterator iter = dict.begin(); iter!=dict.end(); iter++)
{
int nLen = (*iter).length();
int nEnd = i+nLen;
if (nEnd> str.length())
{
continue;
}
if (bAry[nEnd])//想一想什么时候发生这种情况
{
continue;
}
if (str.substr(i,nLen) == *iter)
{
bAry[nEnd] = true;
}
}
}
return bAry[str.length()];
}
@R_936_1304@为O(str.length()*dict.size())。
即使是形如如下的特殊情况,该方法仍然能很好的进行判断字符串是否能被字典分割。
输入: "PRogramcreek", ["programcree","program","creek"].
3.更多有趣的问题
动态规划的方法虽然可以判断一个字符串S是否可以被给定的字典里的单词分割，但却不能够获悉到底是分割成了什么哪些单词。那么如何解决这个问题呢？
一个可行的办法（From jk451）如下：
将数组布尔数组bAry换做整形数组nAray。
1、将bAry[nEnd)=true替换为nAry[nEnd)=i,这意味着当你找到一个0到nEnd位置的子串可分割时，你能够得到改子串分割成的最后单词是i到nEnd位置的字母所组成的单词；
2、如果断定字符串S能够分割成为字典中的单词，那么只需要检查nAry[s.length()]里面的值，分割成的最后一个单词必然是从nAry[s.length()]到s.length()-1的位置中的字母组合成的单词，重复这个过程，可以获得其它的单词。
一点补充：当然你会发现字符串S可分割情况并不是唯一的，例如，S="nihaonihao“，字典dict=｛"ni","nihao","hao"} .此时可以分成{ "nihao","nihao"} 、{ "ni","hao","nihao"} /.......等多种情况。
更多 0
上一篇寻找最长回文子串
给定一个字符串S，同时给定一个字典dict，判断字符串S是否可以被分割为一个个字典里面的单词，也就是判断字符串S是否有字典里面的单词链接而成的。
例如，给定：
s = “leetcode”,
dict = ["leet", "code"].
则结果为真，因为字符串S可以分割为leet 和code两个合法单词。
1.普通方法
[html]
bool WordBreakHelper(string& str, setstring> & dict, int nStart)
{
if (nStart == str.length())
{
return true;
}
for (setstring> ::iterator iter=dict.begin(); iter != dict.end(); iter++)
{
int nLen = (*iter).length();
int nEnd = nStart + nLen;
if (nEnd > str.length())
{
//单词太长直接超过了str字符串剩余部分长度。因此不可能在字符串Str中
continue;
}
if(str.substr(nStart,nLen) == *iter)
{
if (WordBreakHelper(str, dict, nStart+nLen))
{
return true; //想一想为什么这么递归
}
}
}
return false;
}
时间负责度是O(n^2)。
2.动态规划的方法
用动态规划的方法来解决单词分割的关键是：
1、定义一个数组t[],t[i]==true代表字符串的前i个字符是可以用给定字典分割的。
2、数组的初始状态为t[0]==true。
[html]
bool WordBreak(string& str, setstring> & dict)
{
bool *bAry = new bool[str.length()+1]; //想一想为什么要加1
memset(bAry,false,str.length()+1);
bAry[0] = true;
for (int i=0; istr.length(); i++)
{
if (!bAry[i])
{
continue;
}
//想一想为什么要在以i代表的位置为立足点对所有可能的单词进行扫描（这很必要）
for (setstring> ::iterator iter = dict.begin(); iter!=dict.end(); iter++)
{
int nLen = (*iter).length();
int nEnd = i+nLen;
if (nEnd> str.length())
{
continue;
}
if (bAry[nEnd])//想一想什么时候发生这种情况
{
continue;
}
if (str.substr(i,nLen) == *iter)
{
bAry[nEnd] = true;
}
}
}
return bAry[str.length()];
}
时间复杂度为O(str.length()*dict.size())。
即使是形如如下的特殊情况,该方法仍然能很好的进行判断字符串是否能被字典分割。
输入: "programcreek", ["programcree","program","creek"].
3.更多有趣的问题
动态规划的方法虽然可以判断一个字符串S是否可以被给定的字典里的单词分割，但却不能够获悉到底是分割成了什么哪些单词。那么如何解决这个问题呢？
一个可行的办法（from jk451）如下：
将数组布尔数组bAry换做整形数组nAray。
1、将bAry[nEnd)=true替换为nAry[nEnd)=i,这意味着当你找到一个0到nEnd位置的子串可分割时，你能够得到改子串分割成的最后单词是i到nEnd位置的字母所组成的单词；
2、如果断定字符串S能够分割成为字典中的单词，那么只需要检查nAry[s.length()]里面的值，分割成的最后一个单词必然是从nAry[s.length()]到s.length()-1的位置中的字母组合成的单词，重复这个过程，可以获得其它的单词。
一点补充：当然你会发现字符串S可分割情况并不是唯一的，例如，S="nihaonihao“，字典dict=｛"ni","nihao","hao"} .此时可以分成{ "nihao","nihao"} 、{ "ni","hao","nihao"} /.......等多种情况。
更多 0
上一篇寻找最长回文子串
觉得可用，就经常来吧！ 欢迎评论哦！ html5教程，巧夺天工，精雕玉琢。小宝典献丑了！
声明：本文内容由网友自发贡献，本站不承担相应法律责任。对本内容有异议或投诉，请联系2913721942#qq.com核实处理，我们将尽快回复您，谢谢合作！
若转载请注明出处： 单词分割
本文地址： https://pptw.com/jishu/586362.html