题目描述
给定一个非空的字符串s，一个非空的字符串list作为字典。通过在s中添加空格可以将s变为由list中的word表示的句子，要求返回所有可能组成的句子。设定list中的word不重复，且每一个word都可以重复使用。
算法一
先来一个暴力的方法，如下图所示：1）用一个currStr记录当前句子，初始为“”，两个指针start、end分别表示当前词word的起始和结束；2）如果word在list中则将其加入currStr中，start = end +1，否则end后移；3）重复 2）操作直到end超出s的范围。4）可以先计算list中最长word 的长度，作为end后移次数的长度限制。
这种算法存在需要对同一子字符串需要重复计算的情况，提交代码时显示Time Limit Exceeded
class Solution {
public static int maxLen = 0;
public List<String> wordBreak(String s, List<String> dict) {
List<String> res = new ArrayList<String>();
if(dict.size() == 0 || s == null || s.length() == 0) return res;
maxLen = getMaxLen(dict);
dfs(s, dict, 0, res);
return res;
}
public void dfs(String s, List<String> dict, int index, List<String> res){
if(index >= s.length()){
res.add(s.trim());
return;
}
for(int i=index+1; (i<=index + maxLen) && (i<=s.length()); i++){
String word = s.substring(index, i);
if(inDict(word, dict)){
String newStr = s.substring(0, i) + " " + s.substring(i, s.length());
dfs(newStr, dict, i+1, res);
}
}
}
public boolean inDict(String w, List<String> s){
for(String str : s){
if(str.equals(w)){
return true;
}
}
return false;
}
public int getMaxLen(List<String> s){
int max = 0;
for(String str:s){
max = max > str.length()?max : str.length();
}
return max;
}
}
算法二
算法一之所以会超时，原因是可能对同一个的子字符串重复计算。例如s = “abcdabccc”,list = {"ab", "cd", "abcd", "ccc"}。当currStr = “ab cd”时，要对剩余子字符串“abccc”计算一次，currStr = “abcd”时，还需要对“abccc”再进行一次计算。这就是所谓的子问题重复的情况了，因此可以用动态规划来解决问题。
用一个Map来存储子字符串和其对应的所有句子组合方式。但对某一个字符串s进行查询时：若Map中包含该字符串的组合方式，则直接返回；否则，对每一个位于s开头且包含于list中的word，计算其剩余子串的句子组合方式，将其与该单词组合成新的句子。
class Solution {
public List<String> wordBreak(String s, List<String> wordDict) {
if(s == null || wordDict == null) return null;
return helper(s, wordDict, new HashMap<String, List<String>>());
}
private List<String> helper(String s, List<String> wordDict,
HashMap<String, List<String>> dp){
if(dp.containsKey(s)) return dp.get(s);
List<String> res = new ArrayList<>();
if(s.length() == 0) {
res.add("");
dp.put("", res);
return res;
}
for(int i=0; i<wordDict.size(); i++) {
String word = wordDict.get(i);
if(s.startsWith(word)) {
List<String> restRes = helper(s.substring(word.length(), s.length()),
wordDict, dp);
if(restRes.size() != 0) {
for(String eleInRest : restRes) {
if(eleInRest.length() == 0) {
res.add(word);
}else{
res.add(word + " " + eleInRest);
}
}
}
}
}
dp.put(s, res);
return res;
}
}