欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

单词分割

程序员文章站 2023-02-28 18:30:54
给定一个字符串s,同时给定一个字典dict,判断字符串s是否可以被分割为一个个字典里面的单词,也就是判断字符串s是否有字典里面的单词链接而成的。   例如,给定:    ...
给定一个字符串s,同时给定一个字典dict,判断字符串s是否可以被分割为一个个字典里面的单词,也就是判断字符串s是否有字典里面的单词链接而成的。

 

例如,给定:

 

        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

上一篇寻找最长回文子串