leetcode140.Word Break II

发表于 更新于 分类于 ，

题目要求

1
2
3
4
5
6
7
8
9
Given a non-empty string s and a dictionary wordDict containing a list of non-empty words, add spaces in s to construct a sentence where each word is a valid dictionary word. You may assume the dictionary does not contain duplicate words.

Return all such possible sentences.

For example, given
s = "catsanddog",
dict = ["cat", "cats", "and", "sand", "dog"].

A solution is ["cats and dog", "cat sand dog"].

现在有一个非空字符串s和一个非空的字典wordDict。现在向s中添加空格从而构成一个句子，其中这个句子的所有单词都存在与wordDic中。字典中不包含重复的单词。

思路和代码

我们只需要每次从当前字符串中进行一次分割，该分割保证前一部分为字典中的一个单词，然后我们将后一部分作为子字符串递归的传入方法获取子字符串的分割。

catsanddog
cat | sanddog
cat | sand | dog
cats | anddog
cats | and | dog

但是单纯的递归会带来超时的情况，尤其是当字典中的单词出现大量包含的情况，如:[a,aa,aaa,aaaa]，而输入为aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
我们可以利用HashMap缓存来解决这个问题，其中key为子字符串，value为其分割的结果的列表。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
private Map<String, List<String>> cache = new HashMap<String, List<String>>();
public List<String> wordBreak(String s, List<String> wordDict) {
    if(cache.containsKey(s)) return cache.get(s);
    List<String> result = new ArrayList<String>();
    if(s.length()==0){
        result.add("");
        return result;
    }
    
    for(String word : wordDict){
        if(s.startsWith(word)){
            List<String> subWords = wordBreak(s.substring(word.length()), wordDict);
            for(String subWord : subWords){
                result.add(word + (subWord.isEmpty() ? "" :" ") + subWord);
            }
            
            
        }
    }
    cache.put(s, result);
    return result;
}