单词拆分(二)

题意

给定一个字典，和一个字符串，把字符串拆分成字典的子集

方法

递归搜索

分析

因为要拆分成字典的子集

所以，字符串的开头一定匹配某个单词

如果我们枚举找到一个单词，也就从这个单词的结尾知道了下一个拆分的位置

对于下一个拆分的位置，操作和初始单词的操作相同，都是从头部开始匹配

所以，整体步骤为

1. 从头部匹配 一个单词
2. 从单词结尾递归进入第一步

这样如果完全匹配，则输出拆分的结果

样例

以样例数据

"nowcoder",["now","coder","no","wcoder"]

为例

代码

class Solution {
public:
    // 原字符串，搜索起始下标，字典，结果数组，当前拼接字符串
    void dfs(string &s,int idx,vector<string>& dic, vector<string>&res, string cur){
        if(idx == s.length()){ // 完成拆分
            res.emplace_back(cur); // 放入拆分后结果
            return ;
        }
        // 字典可能有重复的内容
        set<int>matchlen; // 一个长度至多匹配一个字典
        for(int i = 0;i < dic.size();i++){ // 尝试字典里每个单词
            if(idx + dic[i].length() > s.length()) continue; // 过长
            bool match = true;
            for(int l = 0;l < dic[i].length();l++){ // 按位匹配
                if(s[idx+l] != dic[i][l]){ // 不匹配
                    match = false;
                    break;
                }
            }
            if(match){ // 匹配
                if(matchlen.count(dic[i].length()))continue; // 重复的单词
                matchlen.insert(dic[i].length()); // 记录
                dfs(s,idx+dic[i].length(),dic,res,(cur.length()==0?"":(cur+" "))+dic[i]); // 递归下一个起始位置
            }
        }
    }
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param s string字符串 
     * @param dic string字符串vector 
     * @return string字符串vector
     */
    vector<string> wordDiv(string s, vector<string>& dic) {
        vector<string> res = {}; // 结果数组
        dfs(s,0,dic,res,"");
        return res;
    }
};

复杂度分析

空间复杂度: 主要消耗在结果的存储,最坏情况所有拆分均合法，空间复杂度为$O(2^n)O(2^n)$

时间复杂度: 对于每一层最坏情况是都有分支，都能匹配，相当于尝试了所有拆分，所以总时间复杂度为$O(2^n)O(2^n)$, 不过本题n很小不会TLE

记忆化搜索

分析

上面的搜索过程中，对于较深的节点，进行了反复搜索

如果把相同的结果进行存储可以优化一定效率

然而不幸的是，本题是方案题而不是统计题，也就是需要提供所有方案，而不只是方案数

所以总的结果代价依然可能高达$2^{n}2^n$

代码

class Solution {
public:
    // 原字符串，搜索起始下标，字典，结果数组，当前拼接字符串
    vector<string> dfs(string &s,int idx,vector<string>& dic,map<int,vector<string> >& mem){
        if(idx == s.length()){
            return {""};
        }
        if(mem.count(idx))return mem[idx]; // 不重复搜索
        vector<string> ret;
        set<int>matchlen; // 字典可能有重复的内容 一个长度至多匹配一个字典
        // 尝试字典里每个单词
        for(int i = 0;i < dic.size();i++){
            if(idx + dic[i].length() > s.length()) continue; // 过长
            bool match = true;
            for(int l = 0;l < dic[i].length();l++){
                if(s[idx+l] != dic[i][l]){ // 不匹配
                    match = false;
                    break;
                }
            }
            if(match){ // 匹配
                if(matchlen.count(dic[i].length()))continue; // 重复的单词
                matchlen.insert(dic[i].length());
                if(idx + dic[i].length() == s.length()){ // 单词匹配到结尾
                    ret.push_back(dic[i]);
                }else{
                    auto strs = dfs(s,idx+dic[i].length(),dic,mem); // 递归
                    for(auto s:strs){
                        ret.push_back(dic[i]+" "+s); // 拼接
                    }
                }
            }
        }
        return mem[idx] = ret; // 记忆化
    }
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param s string字符串 
     * @param dic string字符串vector 
     * @return string字符串vector
     */
    vector<string> wordDiv(string s, vector<string>& dic) {
        map<int,vector<string> > mem; // 记忆结果，保存从 idx 开始向后的匹配结果
        return dfs(s,0,dic,mem);
    }
};

复杂度分析

空间复杂度: 主要消耗在结果的存储,最坏情况所有拆分均合法，空间复杂度为$O(2^n)O(2^n)$

时间复杂度: 对于每一层最坏情况是都有分支，都能匹配，即使有记忆化，返回的不同结果依然需要不同的拼接，所以总时间复杂度为$O(2^n)O(2^n)$