Word Break

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”].

https://leetcode.com/problems/word-break-ii/

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

        List<String>[] dp = new ArrayList[s.length() + 1];
        dp[0] = new ArrayList<String>();

        for(int i = 0; i < s.length(); ++i) {
            if(dp[i] == null) continue;
            for(String word : dict) {
                int len = word.length();
                if(i + len <= s.length() && word.equals(s.substring(i, i + len))) {
                    if(dp[i + len] == null)
                        dp[i + len] = new ArrayList<String>();
                    dp[i + len].add(word);
                }
            }
        }

        if(dp[s.length()] == null) return result;

        dfs(result, dp, new ArrayList<String>(), s.length());
        return result;
    }

    private void dfs(List<String> result, List<String>[] dp, List<String> list, int end) {
        if(end <= 0) {
            StringBuilder s = new StringBuilder();
            for(int i = list.size() - 1; i >= 0; --i) {
                if(i != list.size() - 1) s.append(' ');
                s.append(list.get(i));
            }
            result.add(s.toString());
            return;
        }

        for(String s : dp[end]) {
            list.add(s);
            dfs(result, dp, list, end - s.length());
            list.remove(list.size() - 1);
        }
    }