单词分割
- 作者: ZCG曳
- 来源: 51数据库
- 2021-10-19
例如，给定：
s = “leetcode”,
dict = ["leet", "code"].
则结果为真，因为字符串s可以分割为leet 和code两个合法单词。
1.普通方法
[html]
bool wordbreakhelper(string& str, set<string>& dict, int nstart)
{
if (nstart == str.length())
{
return true;
}
for (set<string>::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, set<string>& dict)
{
bool *bary = new bool[str.length()+1];//想一想为什么要加1
memset(bary,false,str.length()+1);
bary[0] = true;
for (int i=0; i<str.length(); i++)
{
if (!bary[i])
{
continue;
}
//想一想为什么要在以i代表的位置为立足点对所有可能的单词进行扫描（这很必要）
for (set<string>::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
上一篇寻找最长回文子串
