Given a non-empty string_s_and a dictionary_wordDict_containing a list of non-empty words, add spaces in _s _to construct a sentence where each word is a valid dictionary word. Return all such possible sentences.

Note:

• The same word in the dictionary may be reused multiple times in the segmentation.
• You may assume the dictionary does not contain duplicate words.

暴力/backtracking，超时

class Solution {
    public List<String> wordBreak(String s, List<String> wordDict) {
        List<String> res = new ArrayList<String>();
        if(s == null || s.length() == 0 || wordDict == null || wordDict.size() == 0)
            return res;

        Set<String> dict = new HashSet<String>();
        for(String w: wordDict)
            dict.add(w);

        helper(res, new StringBuilder(), dict, 0, s);

        return res;
    }

    public void helper(List<String> res, StringBuilder sb, Set<String> dict, int index, String s) {
        if(index == s.length()) {
            res.add(sb.toString().substring(0, sb.length() - 1));
            return;
        }

        for(int i = index + 1; i <= s.length(); i++) {
            String next = s.substring(index, i);

            if(dict.contains(next)) {
                int len = sb.length();
                sb.append(next).append(" ");
                helper(res, sb, dict, i, s);
                sb.setLength(len);
            }
        }
    }
}

memoization，答案里的一种方法，可以避免重复的遍历

class Solution {
    public List<String> wordBreak(String s, List<String> wordDict) {
        List<String> res = new ArrayList<String>();
        if(s == null || s.length() == 0 || wordDict == null || wordDict.size() == 0)
            return res;

        Set<String> dict = new HashSet<String>();
        for(String w: wordDict)
            dict.add(w);

        HashMap<Integer, List<String>> map = new HashMap<>();

        return helper(map, dict, 0, s);
    }

    public List<String> helper(HashMap<Integer, List<String>> map, Set<String> dict, int index, String s) {
        if(map.containsKey(index)) {
            return map.get(index);
        }

        List<String> res = new ArrayList<>();
        if(index == s.length()) {
            res.add("");
        }

        for(int i = index + 1; i <= s.length(); i++) {
            if(dict.contains(s.substring(index, i))) {
                List<String> list = helper(map, dict, i, s);
                for(String l: list) {
                    res.add(s.substring(index, i) + (l.equals("") ? "" : " ") + l);
                }
            }
        }

        map.put(index, res);

        return res;
    }
}

DP，也是答案里的，但是似乎依然超时

class Solution {
    public List<String> wordBreak(String s, List<String> wordDict) {
        List<String> res = new ArrayList<String>();
        if(s == null || s.length() == 0 || wordDict == null || wordDict.size() == 0)
            return res;

        Set<String> dict = new HashSet<String>();
        for(String w: wordDict)
            dict.add(w);

        ArrayList<String>[] dp = new ArrayList[s.length() + 1];
        ArrayList<String> first = new ArrayList<>();
        first.add("");

        dp[0] = first;

        for(int i = 1; i <= s.length(); i++) {
            ArrayList<String> list = new ArrayList<>();
            for(int j = 0; j < i; j++) {
                if(dp[j].size() > 0 && dict.contains(s.substring(j, i))) {
                    for(String str: dp[j]) {
                        list.add(str + (str.equals("") ? "" : " ") + s.substring(j, i));
                    }
                }
            }

            dp[i] = list;
        }

        return dp[s.length()];
    }
}