单词拆分

给定一个非空字符串 s 和一个包含非空单词的列表 wordDict，判定 s 是否可以被空格拆分为一个或多个在字典中出现的单词。
说明：
拆分时可以重复使用字典中的单词。
你可以假设字典中没有重复的单词。

示例 1：
输入: s = “leetcode”, wordDict = [“leet”, “code”]
输出: true
解释: 返回 true 因为 “leetcode” 可以被拆分成 “leet code”。
示例 2：
输入: s = “applepenapple”, wordDict = [“apple”, “pen”]
输出: true
解释: 返回 true 因为 “applepenapple” 可以被拆分成 “apple pen apple”。
注意你可以重复使用字典中的单词。
示例 3：
输入: s = “catsandog”, wordDict = [“cats”, “dog”, “sand”, “and”, “cat”]
输出: false

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/word-break

思路一 暴力

class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        boolean flag = false;
        for(int i=0;i<s.length()-1;i++){
            for(int j=1;j<s.length()-i;j++){
                if(wordDict.contains(s.substring(i,i+j))){
                    i = i+j;
                    flag = true;
                }
                continue;
            }
            if(!flag){
                return false;
            }
        }
        return true;
    }
}

结果只通过29 / 42 个通过测试用例

分析

当s=”catsandog”, wordDict=[“cats”,”dog”,”sand”,”and”,”cat”]时, 我们如果去匹配cat，sand那么s中剩余的字符串就是og，这无法与字典中剩余的字符相匹配。也就是说，同一个字符串可能有多种匹配结果，而且在匹配完全之前无法得知哪种是正确的，也不知道当前的子串可以匹配的单词有多长，往这个方向思考下去就是回溯法与剪枝的思路了。

思路二 回溯

class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        HashSet<String> set = new HashSet<String>(wordDict);
        return backtrack(s, set);
    }
    public static boolean backtrack(String s, HashSet<String> set){
        if(s==null||s.length()==0) return true;
        for(int i=0;i<s.length();i++){
            if(set.contains(s.substring(0, i+1))){
                if(backtrack(s.substring(i+1), set)){
                    return true;
                }
            }
        }
        return false;
    }
}

结果时间超时

分析

首先将字典List加入到HashSet当中。逐个增加单词的字符数量，直到字典中有了该单词之后，递归判断剩下的字符串，如果无法匹配返回false，如果最后剩下空字符串说明全部匹配成功返回true。
这样会有很多重复的计算，因此想到记忆化回溯。

思路三 记忆化回溯

分析

增加一个boolean数组表示当前位置之后的字符串是否遍历过了，如果遍历过了并且没有提前递归的返回true，说明这个位置后面的匹配不会成功，因此直接返回false。

class Solution {
    boolean[] flag;
    public boolean wordBreak(String s, List<String> wordDict) {
        this.flag = new boolean[s.length()];
        HashSet<String> set = new HashSet<String>(wordDict);
        return backtrack(s, 0, set);
    }
    public boolean backtrack(String s, int start, HashSet<String> set){
        if(s==null||s.length()==0) return true;
        if(flag[start]) return false;
        for(int i=0;i<s.length();i++){
            if(set.contains(s.substring(0, i+1))){
                if(backtrack(s.substring(i+1), start+i, set)){
                    return true;
                }
            }
        }
        flag[start] = true;
        return false;
    }
}

思路四 动态规划

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