public List<String> wordBreak(String s, List<String> wordDict) {
    //集合Set的查找效率要比集合list高，这里为了提高效率，
    //先把list转化为集合set
    Set<String> set = new HashSet<>(wordDict);
    //下面是动态规划方式，判断字符串被拆解的子串是否都在字典中
    int length = s.length();
    boolean[] dp = new boolean[length + 1];
    dp[0] = true;//边界条件
    for (int i = 1; i <= length; i++) {
        for (int j = 0; j < i; j++) {
            dp[i] = dp[j] && set.contains(s.substring(j, i));
            if (dp[i]) {
                break;
            }
        }
    }
    List<String> res = new ArrayList<>();
    //如果不能拆解，直接返回空的集合就行了
    if (!dp[length])
        return res;
    //如果能被拆解，我们通过回溯方式执行拆解
    traceback(s, set, 0, res, new ArrayList<>());
    return res;
}

//回溯方式拆解字符串
private void traceback(String s, Set<String> wordDict, int start, List<String> res, List<String> path) {
    if (start == s.length()) {
        //下面这两行代码都是字符串加空格然后拼接，一个是官方提供的方法，
        //一个是我自己写的，都可以实现
        //res.add(String.join(" ", path));
        res.add(join(path));
        return;
    }
    for (int i = start + 1; i <= s.length(); i++) {
        //拆解字符串
        String str = s.substring(start, i);
        //如果拆解的子串不存在于字典中，就继续扩大子串
        if (!wordDict.contains(str))
            continue;
        //如果拆解的子串存在于字典中，就把子串添加到path中
        path.add(str);
        //往下继续递归
        traceback(s, wordDict, i, res, path);
        //执行回溯，把之前添加的子串给移除
        path.remove(path.size() - 1);
    }
}

//字符串加空格拼接
private String join(List<String> path) {
    StringBuilder stringBuilder = new StringBuilder();
    for (int i = 0; i < path.size(); i++) {
        stringBuilder.append(path.get(i));
        if (i != path.size() - 1)
            stringBuilder.append(" ");
    }
    return stringBuilder.toString();
}

DFS解决

回溯算法比较容易理解，这题我们还可以使用DFS来解决。比如我们进行截取的时候，如果截取的子串存在于字典中，我们通过递归的方式拆分剩下的，如果剩下的能够拆分我们就把当前拆分的子串和剩下拆分的结果进行拼接，如果剩下的不能拆分，不会进行任何拼接，直接返回空的集合即可，其实这种思路还可以借鉴《464. BFS和DFS解二叉树的所有路径》的最后一种解法，实现原理如下所示

来看下代码

public List<String> wordBreak(String s, List<String> wordDict) {
    return backtrack(s, new HashSet<>(wordDict), 0);
}

public List<String> backtrack(String s, Set<String> wordDict, int start) {
    List<String> res = new ArrayList<>();
    for (int i = start + 1; i <= s.length(); i++) {
        String str = s.substring(start, i);
        //如果拆解的子串不存在于字典中，就继续拆
        if (!wordDict.contains(str))
            continue;
        //走到下面这个地方，说明拆分的子串str存在于字典中
        //如果正好拆完了，我们直接把最后一个子串添加到res中返回
        if (i == s.length())
            res.add(str);
        else {
            //如果没有拆完，我们对剩下的子串继续拆分
            List<String> remainRes = backtrack(s, wordDict, i);
            //然后用当前的子串str和剩下的子串进行拼接（注意如果剩下的子串不能
            //完全拆分，remainRes就会为空，就不会进行拼接）
            for (String remainStr : remainRes) {
                res.add(str + " " + remainStr);
            }
        }
    }
    return res;
}