Word Break II(Hard)

Given a string s and a dictionary of words dict, add spaces in s to construct a sentence where each word is a valid dictionary word.

Return all such possible sentences.

For example, given s = "catsanddog", dict = ["cat", "cats", "and", "sand", "dog"].

A solution is ["cats and dog", "cat sand dog"].

解题思路1：DFS+回溯

 public List<String> wordBreak(String s, Set<String> dict) {
    List<String> result = new ArrayList<String>();

    if (s == null || s.length() == 0 || dict == null || dict.size() == 0) {
        return result;
    }

        List<String> curr = new ArrayList<String>();
        wordBreakHelper(0, s, dict, curr, result);

        return result;
}

private void wordBreakHelper(int start, String s, Set<String> dict, List<String> curr, List<String> result) {
    if (start >= s.length()) {
        String temp = constructString(curr);
        result.add(temp);
    }

    for (int i = start; i < s.length(); i++) {
        if (dict.contains(s.substring(start, i + 1))) {
            curr.add(s.substring(start, i + 1));
            wordBreakHelper(i + 1, s, dict, curr, result);
            curr.remove(curr.size() - 1);
        }
    }
}

private String constructString(List<String> tokens) {
        StringBuilder sb = new StringBuilder();

        for (int i = 0; i < tokens.size() - 1; i++) {
            sb.append(tokens.get(i) + " ");
        }

        sb.append(tokens.get(tokens.size() - 1));

        return sb.toString();
}

时间复制度：O(2^n),空间复杂度O(n)

解题思路2:动态规划

public List<String> wordBreak(String s, Set<String> wordDict) {
        // 判断是否能够分解
        if (!helper(s, wordDict)) {
            return new ArrayList<String>();
        }

        //记录字符串s.substring(0, i)对应的解
        HashMap<Integer, List<String>> map = new HashMap<Integer, List<String>>();
        map.put(0, new ArrayList<>());
        map.get(0).add("");

        for (int i = 1; i <= s.length(); i++) {
            for (int j = 0; j < i; j++) {
                if (map.containsKey(j) && wordDict.contains(s.substring(j, i))) {
                    if (!map.containsKey(i))
                        map.put(i, new ArrayList<>());

                    for (String str : map.get(j)) {
                        map.get(i).add(str + (str.equals("") ? "" : " ") + s.substring(j, i));
                    }
                }
            }
        }

        return map.get(s.length());
    }

    private boolean helper(String s, Set<String> wordDict) {
        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++) {
                if (dp[j] && wordDict.contains(s.substring(j, i))) {
                    dp[i] = true;
                }
            }
        }
        return dp[s.length()];
    }

    public static void main(String[] args) {
        Test instance = new Test();

        int[] num = {5, 1, 2, 3, 4};

        String s = "catsanddog";
        Set<String> dict = new HashSet<String>();
        dict.add("cat");
        dict.add("cats");
        dict.add("and");
        dict.add("sand");
        dict.add("dog");

        List<String> result = instance.wordBreak(s, dict);

        for (String str : result) {
            System.out.println("Result is " + str);
        }
    }

时间复制度：O(k*n^2),空间复杂度O(nk)