题解 | #单词拆分(二)#

单词拆分(二)

http://www.nowcoder.com/practice/bb40e0aae84a4491a35f93b322516cb5

题意理解

把一个字符串s拆分为若干个子串,要求每个子串都是数组dic中的某个元素。拆分的方***有多种,要求输出所有的方法,每一种拆分方法用空格将子串隔开从而形成一个字符串。

方法一

深度优先搜索
看到题目要求的数据较小,考虑使用深度优先搜索枚举所有的可能性。如果s可以被正确拆分,说明其头部的一段子串是dic中的元素。

每次搜索时,遍历dic数组。对于其中的每个元素,判断它和s的头部等长的子串是否相同。
1、如果相同:把s头部对应的子串剔除,拆分剩余的部分remain,进入递归;
2、如果不同,判断dic中下一个元素。
边界条件:s为空,说明s被拆分完毕。

由于dic中可能出现重复的元素,会导致最后得到的拆分种类重复,需要先将dic中重复的元素剔除。但是dic中的一个元素可以重复利用。这两点不矛盾。

以"nowcoder",["now","oder","coder"]为例,过程如下: alt

具体代码如下:

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
     *
     * 
     * @param s string字符串 
     * @param dic string字符串vector 
     * @return string字符串vector
     */
    vector<string> ans;
    void dfs(vector<string>& dic, string remain, string ss)
    {
        if (remain=="")
        {
            //删除最后一个空格
            ss.pop_back();
            ans.push_back(ss);
            return;
        }
        //遍历dic数组中每个元素
        for (int i=0;i<dic.size();i++)
        {
            string sub_str = remain.substr(0,dic[i].size());
            //匹配成功
            if (sub_str == dic[i])
            {
                //在传参时进行remain和ss的更新
                dfs(dic, remain.substr(dic[i].size(),remain.size()-dic[i].size()), ss+sub_str+" ");
            }
        }
        return;
    }
    
    vector<string> wordDiv(string s, vector<string>& dic) {
        // write code here
        unordered_map<string, bool> repeat;
        for (int i=0;i<dic.size();i++)
        {
            if (repeat[dic[i]]) {dic.erase(dic.begin()+i); i--;}
            else repeat[dic[i]] = true;
        }
        dfs(dic, s, "");
        return ans;
    }
};

时间复杂度: O(NN)O(N^N)。最坏的情况,每次只匹配s中的第0个字符,每次匹配需要遍历一遍dic。s和dic的长度均为N。
空间复杂度: O(N)O(N)。递归的深度最多和s一样长,开辟的新空间repeat、ss等长度至多为N。

方法二

动态规划
使用二维数组ans记录,s[0~i]可以被拆分的所有方法,即ans的每个元素对应s[0~i]拆分的答案(元素类型为string的一维数组)。

要求ans[i],此时ans[0]~ans[i-1]均已知。如果s[j~i]是dic中的元素,则ans[i]的拆分方法里要包含ans[j-1]+" "+s[j~i],这里j可以从0取到i。当j为0时,直接将s[0~i]做为ans[i]的一种拆分方法即可。

状态转移方程为,这里的求和符号对应数组push_back操作:
ans[i]=j=1ik=0ans[j1](ans[j1][k]+s[i...j])ans[i] = \sum_{j=1}^i\sum_{k=0}^{|ans[j-1]|} (ans[j-1][k]+s[i...j])

以为"nowcoder",["now","no","coder","w"]例,ans结果如图所示: alt

具体代码如下:

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
     *
     * 
     * @param s string字符串 
     * @param dic string字符串vector 
     * @return string字符串vector
     */
    
    vector<string> wordDiv(string s, vector<string>& dic) {
        // write code here
        //dictionary记录dic中有哪些元素
        unordered_map<string, bool> dictionary;
        //ans[i]表示s[0]~s[i]拆分的所有情况
        vector<vector<string>> ans(s.size());
        for (int i=0;i<dic.size();i++)
        {
            dictionary[dic[i]] = true;
        }
        for (int i=0;i<s.size();i++)
        {
            for (int j=0;j<=i;j++)
            {
                if (dictionary[s.substr(j,i-j+1)])
                {
                    //j==0时要特殊处理
                    if (!j) ans[i].push_back(s.substr(j,i-j+1));
                    else
                    {
                        for (int k=0;k<ans[j-1].size();k++)
                        {
                            //当前拆分方法如何得到
                            ans[i].push_back(ans[j-1][k] + " " + s.substr(j,i-j+1));
                        }
                    }
                }
            }
        }
        return ans[s.size()-1];
    }
};

时间复杂度: O(N22N)O(N^2*2^N)。外面是双重循环,每个循环的长度为N;最内侧的第三重循环遍历的是之前拆分的种数,对于长度为N的字符串来讲最多有2N2^N种。
空间复杂度: O(N2N)O(N*2^N)。ans有N行,每行最多可能包含了2N2^N种拆分方法

全部评论

相关推荐

鼗:四级有点难绷,感觉能拿国家励志奖学金,学习能力应该蛮强的,四级确实不重要,但是拿这个卡你可是很恶心啊
点赞 评论 收藏
分享
2 收藏 评论
分享
牛客网
牛客企业服务