140. Word Break II(#1 ).java

public class Solution {
    public List<String> wordBreak(String s, List<String> wordDict) {
        List<String> res = new ArrayList<String>();
        if (s == null || s.length() == 0) {
            return res;
        }
        int max = 0;
        for (String str : wordDict) {
            max = Math.max(str.length(), max);
        }
        boolean[] table = new boolean[s.length() + 1];
        table[0] = true;
        for (int i = 1; i < table.length; i++) {
            for (int j = i - 1; j >= 0 && i - j <= max; j--) {
                if (table[j] && wordDict.contains(s.substring(j, i))) {
                    table[i] = true;
                }
            }
        }
        List<String> list = new ArrayList<>();
        dfs(s, "", table, wordDict, list);
        return list;
    }
    
    public void dfs(String s, String path, boolean[] table, List<String> wordDict, List<String> list) {
        if (s.length() == 0) {
            list.add(path);
            return;
        }
        for (int i = 0; i < s.length(); i++) {
            if (table[i] && wordDict.contains(s.substring(i))) {
                String newPath = null;
                if (path == "") {
                    newPath = s.substring(i);    
                } else {
                    newPath = s.substring(i) + " " + path;    
                }
                dfs(s.substring(0, i), newPath, table, wordDict, list);
            }
        }
    }
}

140. Word Break II(#2 ).java

public class Solution {
    public List<String> wordBreak(String s, List<String> wordDict) {
        List<String> res = new ArrayList<String>();
        if (s == null || s.length() == 0) {
            return res;
        }
        int max = 0;
        for (String str : wordDict) {
            max = Math.max(str.length(), max);
        }
        boolean[] table = new boolean[s.length() + 1];
        table[0] = true;
        for (int i = 1; i < table.length; i++) {
            for (int j = i - 1; j >= 0 && i - j <= max; j--) {
                if (table[j] && wordDict.contains(s.substring(j, i))) {
                    table[i] = true;
                }
            }
        }
        Map<String, List<String>> map = new HashMap<String, List<String>>();
        return dfs(s, table, wordDict, map);
    }
    
    public List<String> dfs(String s, boolean[] table, List<String> wordDict, Map<String, List<String>> map) {
        List<String> res = new ArrayList<>();
        if (s.length() == 0) {
            res.add("");
            return res;
        }
        if (map.containsKey(s)) {
            return map.get(s);
        }
        for (int i = 0; i <= s.length(); i++) {
            if (table[i] && wordDict.contains(s.substring(i))) {
                List<String> subres = dfs(s.substring(0, i), table, wordDict, map);
                for (String str : subres) {
                    if (str.equals("")) {
                        res.add(s.substring(i));
                    } else {
                        res.add(str + " " + s.substring(i));    
                    }
                }
            }
        }
        map.put(s, res);
        return res;
    }
}