题目描述(中等难度)

给一个字符串,和一些单词,问字符串能不能由这些单词构成。每个单词可以用多次,也可以不用。

解法一 回溯

来一个简单粗暴的方法,利用回溯法,用 wordDict 去生成所有可能的字符串。期间如果出现了目标字符串 s,就返回 true

public boolean wordBreak(String s, List<String> wordDict) {
    return wordBreakHelper(s,wordDict,"");
}
//temp 是当前生成的字符串
private boolean wordBreakHelper(String s, List<String> wordDict, String temp) {
    //如果此时生成的字符串长度够了,就判断和目标字符日是否相等
    if(temp.length() == s.length()){
        if(temp.equals(s)){
            return true;
        }else{
            return false;
        }
    }
    //长度超了,就返回 false
    if(temp.length() > s.length()){
        return false;
    }
    //考虑每个单词
    for(int i = 0;i < wordDict.size(); i++){
        if(wordBreakHelper(s,wordDict,temp + wordDict.get(i))){
            return true;
        }
    }
    return false;
}

意料之中,超时了

让我们考虑优化的方法。

在递归出口的地方优化一下。

之前是在长度相等的时候,开始判断字符串是否相等。

很明显,字符串长度相等之前我们其实就可以判断当前是不是符合了。

例如 temp = "abc",如果 s = "dddefg",虽然此时 temps 的长度不相等。但因为前缀已经不同,所以后边无论是什么都不可以了。此时就可以返回 false 了。

所以递归出口可以从头判断每个字符是否相等,不相等就直接返回 false

for (int i = 0; i < temp.length(); i++) {
    if (s.charAt(i) != temp.charAt(i)) {
        return false;
    }
}

然后代码就是下边的样子。

public boolean wordBreak(String s, List<String> wordDict) {
    return wordBreakHelper(s, wordDict, "");
}

private boolean wordBreakHelper(String s, List<String> wordDict, String temp) {
    if (temp.length() > s.length()) {
        return false;
    }
    //判断此时对应的字符是否全部相等
    for (int i = 0; i < temp.length(); i++) {
        if (s.charAt(i) != temp.charAt(i)) {
            return false;
        }
    }
    if (s.length() == temp.length()) {
        return true;
    }
    for (int i = 0; i < wordDict.size(); i++) {
        if (wordBreakHelper(s, wordDict, temp + wordDict.get(i))) {
            return true;
        }
    }
    return false;
}

遗憾的是,依旧是超时

发现上边的例子答案很明显是 false,因为 s 中的 b 字母在 wordDict 中并没有出现。

所以我们可以先遍历一遍 swordDict ,从而确定 s 中的字符是否在 wordDict 中存在,如果不存在可以提前返回 false

所以代码可以继续优化。

public boolean wordBreak(String s, List<String> wordDict) {
    HashSet<Character> set = new HashSet<>();
    //将 wordDict 的每个字母放到 set 中
    for (int i = 0; i < wordDict.size(); i++) {
        String t = wordDict.get(i);
        for (int j = 0; j < t.length(); j++) {
            set.add(t.charAt(j));
        }
    }
    //判断 s 的每个字母在 set 中是否存在
    for (int i = 0; i < s.length(); i++) {
        if (!set.contains(s.charAt(i))) {
            return false;
        }
    }
    return wordBreakHelper(s, wordDict, "");
}

private boolean wordBreakHelper(String s, List<String> wordDict, String temp) {
    if (temp.length() > s.length()) {
        return false;
    }
    for (int i = 0; i < temp.length(); i++) {
        if (s.charAt(i) != temp.charAt(i)) {
            return false;
        }
    }
    if (s.length() == temp.length()) {
        return true;
    }
    for (int i = 0; i < wordDict.size(); i++) {
        if (wordBreakHelper(s, wordDict, temp + wordDict.get(i))) {
            return true;
        }
    }
    return false;
}

令人悲伤的是

还有 5test 没有通过。还有什么可以优化的地方呢?

是时候拿出绝招了,在前边的题已经用过很多很多次,memoization 技术。思想就是把回溯中已经考虑过的解存起来,第二次回溯过来的时候可以直接使用。

这里的话,我们可以用一个 HashMapkey 的话就存 tempvalue 的话就代表以当前 temp 开始的字符串,经过后边的尝试是否能达到目标字符串 s

public boolean wordBreak(String s, List<String> wordDict) {
    HashSet<Character> set = new HashSet<>();
    for (int i = 0; i < wordDict.size(); i++) {
        String t = wordDict.get(i);
        for (int j = 0; j < t.length(); j++) {
            set.add(t.charAt(j));
        }
    }
    for (int i = 0; i < s.length(); i++) {
        if (!set.contains(s.charAt(i))) {
            return false;
        }
    }
    return wordBreakHelper(s, wordDict, "", new HashMap<String,Boolean>());
}

private boolean wordBreakHelper(String s, List<String> wordDict, String temp, HashMap<String, Boolean> hashMap) {
    if (temp.length() > s.length()) {
        return false;
    }
    //之前是否存过
    if(hashMap.containsKey(temp)){
        return hashMap.get(temp);
    }
    for (int i = 0; i < temp.length(); i++) {
        if (s.charAt(i) != temp.charAt(i)) {
            return false;
        }
    }
    if (s.length() == temp.length()) {
        return true;
    }
    for (int i = 0; i < wordDict.size(); i++) {
        if (wordBreakHelper(s, wordDict, temp + wordDict.get(i), hashMap)) {
            //结果放入 hashMap
            hashMap.put(temp, true);
            return true;
        }
    }
    //结果放入 hashMap
    hashMap.put(temp, false);
    return false;
}

这次就成功通过了。

解法二 分治

换一种思想,分治,也就是大问题转换为小问题,通过小问题来解决。

这个想法前边已经做过很多很多题了,大家可以参考 97 题115 题 等等。

我们现在要判断目标串 s 是否能由 wordDict 构成。

我们用 dp[i,j),表示从 s 的第 i 个字符开始,到第 j 个字符的前一个结束的字符串是否能由 wordDict 构成。

假如我们知道了 dp[0,1) dp[0,2) dp[0,3)...dp[0,len - 1) ,也就是除 s 本身的所有子串是否能由 wordDict 构成。

那么我们就可以知道

dp[0,len) =  dp[0,1) && wordDict.contains(s[i,len))
            || dp[0,2) && wordDict.contains(s[2,len))
            || dp[0,3) && wordDict.contains(s[3,len))   
            ...
            || dp[0,len - 1) && wordDict.contains(s[len - 1,len))

dp[0,len) 就代表着 s 是否能由 wordDict 构成。有了上边的转移方程,就可以用递归写出来了。

public boolean 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);
}

private boolean wordBreakHelper(String s, HashSet<String> set) {
    if (s.length() == 0) {
        return true;
    }
    for (int i = 0; i < s.length(); i++) {
        if (set.contains(s.substring(i, s.length())) && wordBreakHelper(s.substring(0, i), set)) {
            return true;
        }
    }
    return false;
}

如果不做任何处理,依旧会得到超时。

所有,memoization 又来了,和之前一样将中间结果存储起来。

public boolean 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, Boolean>());
}

private boolean wordBreakHelper(String s, HashSet<String> set, HashMap<String, Boolean> map) {
    if (s.length() == 0) {
        return true;
    }
    if (map.containsKey(s)) {
        return map.get(s);
    }
    for (int i = 0; i < s.length(); i++) {
        if (set.contains(s.substring(i, s.length())) && wordBreakHelper(s.substring(0, i), set, map)) {
            map.put(s, true);
            return true;
        }
    }
    map.put(s, false);
    return false;
}

当然除了递归中存储,我们也可以直接用动态规划的思想,求一个结果就保存一个结果。

dp[i] 表示字符串 s[0,i) 能否由 wordDict 构成。

public boolean wordBreak(String s, List<String> wordDict) {
    HashSet<String> set = new HashSet<>();
    for (int i = 0; i < wordDict.size(); i++) {
        set.add(wordDict.get(i));
    }
    boolean[] dp = new boolean[s.length() + 1];
    dp[0] = true;
    for (int i = 1; i <= s.length(); i++) {
        for (int j = 0; j < i; j++) {
            dp[i] = dp[j] && wordDict.contains(s.substring(j, i));
            if (dp[i]) {
                break;
            }
        }
    }
    return dp[s.length()];
}

解法一的回溯优化主要就是剪枝,让一些提前知道结果的解直接结束,不进入递归。解法二的想法,就太常用了,从递归到 memoization 再到动态规划,其实本质都是一样的。

results matching ""

    No results matching ""