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

单词拆分(二)

题目描述

给定一个字符串 s 和一个字符串数组 dic ，在字符串 s 的任意位置添加任意多个空格后得到的字符串集合是给定字符串数组 dic 的子集（即拆分后的字符串集合中的所有字符串都在 dic 数组中），你可以以任意顺序 返回所有这些可能的拆分方案。

方法一：递归的方法

解题思路

对于本题，采用递归的方法进行求解，首先从头部匹配一个单词，然后从该单词的结尾在进行匹配找到另一个单词，最后输出能够完全匹配的结果。

解题代码

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]); // 递归下一个起始位置
            }
        }
    }
    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)$

方法二：java的方法

解题思路

思路同方法一。

解题代码

import java.util.*;

public class Solution {
    HashMap mp=new HashMap<String,Integer>();//判断某字符串是否存在
    int len;
    Vector<String> res=new Vector<String>();
    public String[] wordDiv (String s, String[] dic)
    {
        int n=dic.length;
        len=s.length();
        for(int i=0;i<n;i++)
        {//初始化
            mp.put(dic[i],1);
        }
        dfs(s,0,"");//递归
        int m=res.size();
        String[] ans=new String[m];
        for(int i=0;i<m;i++)
        {
            ans[i]=res.get(i);
        }
        return ans;
    }
    void dfs(String s,int st,String str)
    {
        if(len==st)
        {//递归结束条件
            res.add(str.substring(0,str.length()-1));
            return;
        }
        String x="";
        for(int i=st;i<len;i++)
        {//循环遍历
            x+=s.charAt(i);
            if(mp.containsKey(x))
            {//如果存在该字符串，则递归
                dfs(s,i+1,str+x+" ");
            }
        }
    }
}

复杂度分析

时间复杂度：最坏情况匹配了所有，因此时间复杂度为$O(2^n)O(2^n)$。

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