刷题第6篇：单词拆分
LeetCode第140题：单词拆分II【困难】【递归】
【题目描述】
题目描述
给定一个字符串和一个字典，然后使用空格进行分割，最后存储所有可能的分割结果。
- 要求被分割的单词都要存在字典中
【解法】：递归
1、解决思路
我们使用递归的方法。每当遍历到一个字典中的单词之后，记录下当前的索引值，然后继续向后遍历。如果遍历到最后一个字符，恰好连接前面的字符，属于字典中的单词，则将此分割方式记录下来。
2、数据结构
- set
- 字符串String，StringBuilder
- 链表list
3、代码实现
public List<String> wordBreak(String s, List<String> wordDict) {
List<String> res = new ArrayList<>();
if (s == null || s.length() == 0) return res;
Set<String> dic = new HashSet<>(wordDict);
int len = s.length();
T140(res,s,dic,len,new StringBuilder(),0,1);
return res;
}
public void T140(List<String> res , String s, Set<String> wordDict,int len,StringBuilder sb,int start,int last){
if (last == len ){//最后一个单词
String word = s.substring(start,last);
if (wordDict.contains(word)){//如果最后一个单词存在，则存储进来
sb.append(word);
res.add(sb.toString());
sb.delete(sb.length()-word.length(),sb.length());//将新加入的单词删除
return ;
}else{
return ;
}
}
String word = s.substring(start,last);
if (wordDict.contains(word) ){
sb.append(word+" ");
T140(res,s,wordDict,len,sb,last,++last);
sb.delete(sb.length()-word.length()-1,sb.length());//将新加入的单词删除
T140(res,s,wordDict,len,sb,start,last);//将单词的距离加大一个单位，寻找新的匹配
}else{//如果不包含此单词，则将单词的长度向后移一位
T140(res,s,wordDict,len,sb,start,++last);
}
}
当我们一切都调通了之后，点击提交，时间超出限制了！
超时了
心中万马奔腾啊！！！！！
然后我们分析一下上面的代码，看看能否进行一些优化。我们发现，当我们查找当前单词不在字典中的时候，我们会将last索引加1，继续增加单词Word的长度。如果我们能够提前记录一下字典中最长单词的长度，就可以避免一些不必要的计算。于是，提前遍历字典，获取所有单词的最长长度，如果当前单词已经长度超过了最长的长度，则提前返回。
下面就是上面代码的升级版本~
public List<String> wordBreak(String s, List<String> wordDict) {
List<String> res = new ArrayList<>();
if (s == null || s.length() == 0) return res;
Set<String> dic = new HashSet<>(wordDict);
int maxLen = 0;//记录字典中最长的单词
for (String s1 : dic) {
if (s1.length() > maxLen){
maxLen = s1.length();
}
}
int len = s.length();
T140(res,s,dic,len,maxLen,new StringBuilder(),0,1);
return res;
}
public void T140(List<String> res , String s, Set<String> wordDict,int len,int maxLen,StringBuilder sb,int start,int last){
if (last == len ){//最后一个单词
String word = s.substring(start,last);
if (wordDict.contains(word)){//如果最后一个单词存在，则存储进来
sb.append(word);
res.add(sb.toString());
sb.delete(sb.length()-word.length(),sb.length());//将新加入的单词删除
return ;
}else{
return ;
}
}
String word = s.substring(start,last);
if (word.length() > maxLen){//如果当前单词的长度已经超过了字典中最长的单词，则直接终止
return;
}
if (wordDict.contains(word) ){
sb.append(word+" ");
T140(res,s,wordDict,len,maxLen,sb,last,++last);
sb.delete(sb.length()-word.length()-1,sb.length());//将新加入的单词删除
T140(res,s,wordDict,len,maxLen,sb,start,last);//将单词的距离加大一个单位，寻找新的匹配
}else{//如果不包含此单词，则将单词的长度向后移一位
T140(res,s,wordDict,len,maxLen,sb,start,++last);
}
}
改好了，然而。。。。。。依旧超时：
又超时了！！！！
思索之后，我们再看看有哪里可以继续优化吧！在使用递归的时候。如果我们将每次分割后存在字典中的单词，使用map缓存起来，这样也可以大大节省后序遍历的次数。每个可以被分割的单词，仅仅让它分割一次，供后序使用。于是，重新写了最终代码：
public List<String> wordBreak(String s, List<String> wordDict) {
HashSet<String> set = new HashSet<>();
for (int i = 0; i < wordDict.size(); i++) {
set.add(wordDict.get(i));
}
return wordBreakHelper(s, set, new HashMap<String, List<String>>());
}
private List<String> wordBreakHelper(String s, HashSet<String> set, HashMap<String, List<String>> map) {
if (s.length() == 0) {
return new ArrayList<>();
}
if (map.containsKey(s)) {
return map.get(s);
}
List<String> res = new ArrayList<>();
for (int j = 0; j < s.length(); j++) {
if (set.contains(s.substring(j, s.length()))) {
if (j == 0) { //空串的情况，直接加入
res.add(s.substring(j, s.length()));
} else {
//递归得到剩余字符串的所有组成可能，然后和当前字符串分别用空格连起来加到结果中
List<String> temp = wordBreakHelper(s.substring(0, j), set, map);
for (int k = 0; k < temp.size(); k++) {
String t = temp.get(k);
res.add(t + " " + s.substring(j, s.length()));
}
}
}
}
//缓存结果
map.put(s, res);
return res;
}
好了，写到这里，终于成功了。最终放在LeetCode上面，AC了！！！！！
ok ! 以上就是本周的内容啦！
本文参与 腾讯云自媒体分享计划，分享自微信公众号。
原始发表：2020-02-23，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录