面试算法-128-单词拆分 II

题目

给定一个字符串 s 和一个字符串字典 wordDict ，在字符串 s 中增加空格来构建一个句子，使得句子中所有的单词都在词典中。以任意顺序 返回所有这些可能的句子。

注意：词典中的同一个单词可能在分段中被重复使用多次。

示例 1：

输入:s = “catsanddog”, wordDict = [“cat”,“cats”,“and”,“sand”,“dog”]
输出:[“cats and dog”,“cat sand dog”]

解

class Solution {
    public List<String> wordBreak(String s, List<String> wordDict) {
        LinkedList<String> path = new LinkedList<>();
        List<String> result = new ArrayList<>();
        dfs(s, wordDict, 0, path, result);
        return result;
    }

    public void dfs(String s, List<String> wordDict, Integer index, LinkedList<String> path,
            List<String> result) {
        if (index == s.length()) {
            result.add(String.join(" ", path));
            return;
        }

        if (index > s.length()) {
            return;
        }

        for (int i = 0; i < wordDict.size(); i++) {
            String item = wordDict.get(i);
            if (s.startsWith(item, index)) {
                path.add(item);
                dfs(s, wordDict, index + item.length(), path, result);
                path.removeLast();
            }
        }

    }
}