题解 | #单词拆分(二)#
单词拆分(二)
https://www.nowcoder.com/practice/bb40e0aae84a4491a35f93b322516cb5?tpId=196&tqId=39340&rp=1&ru=/exam/oj&qru=/exam/oj&sourceUrl=%2Fexam%2Foj%3Ftab%3D%25E7%25AE%2597%25E6%25B3%2595%25E7%25AF%2587%26topicId%3D196%26page%3D1%26search%3Dnc182&difficulty=undefined&judgeStatus=undefined&tags=&title=nc182
题意：
给定一个字符串和一个字符串数组，在字符串的任意位置添加空格后得到的字符串集合是给定字符串数组的子集，请输出可能的拆分方案。
对答案按字典序排序后输出，空格视为一个字符。
方法一：
递归
思路：首先，用无序map实现判断某字符串是否存在的作用。
然后，按照以下树形图解递归遍历字符串；
最后，返回答案即可。
class Solution {
public:
unordered_map<string,int> mp;//判断某字符串是否存在
int len;
vector<string> res;
vector<string> wordDiv(string s, vector<string>& dic) {
int n=dic.size();
len=s.size();
for(int i=0;i<n;i++){//初始化
mp[dic[i]]=1;
}
dfs(s,0,"");//递归
return res;
}
void dfs(string s,int st,string str){
if(len==st){//递归结束条件
res.push_back(str.substr(0,str.size()-1));
return;
}
string x="";
for(int i=st;i<len;i++){//循环遍历
x+=s[i];
if(mp.count(x)){//如果存在该字符串，则递归
dfs(s,i+1,str+x+" ");
}
}
}
};
时间复杂度：%2C%E9%80%92%E5%BD%92%E5%9B%9E%E6%BA%AF%E6%A0%91%E5%BD%A2%E7%BB%93%E6%9E%84%2Cn%E6%98%AF%E9%81%8D%E5%8E%86%E5%AD%97%E7%AC%A6%E4%B8%B2s%2C%202%5E%7Bn%7D%E6%98%AF%E5%AF%B9%E5%AD%97%E7%AC%A6%E4%B8%B2s%E7%9A%84%E5%88%86%E5%89%B2%E6%96%B9%E5%BC%8F%E3%80%82)
空间复杂度：%2C%E5%AD%98%E5%82%A8%E6%97%A0%E5%BA%8Fmap%E5%92%8C%E9%80%92%E5%BD%92%E6%A0%88%E6%B7%B1%E5%BA%A6%E3%80%82)
方法二：
java
思路：同方法一思路相同，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+" ");
}
}
}
}
时间复杂度：空间复杂度：
投递美团等公司7个岗位 >
