Word Break II

140. Word Break II

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. You may assume the dictionary does not contain duplicate words.

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

public class Solution {
    public List<String> wordBreak(String s, List<String> wordDict) {
        List<String> result = new ArrayList<>();
        
        if (s == null || s.length() == 0) {
            return result;
        }
        
        if (wordBreakcheck(s, wordDict)) {
            wordBreakHelper(s, wordDict, result, "", 0);
        }
        
        return result;
    }
    
    private boolean wordBreakcheck(String s, List<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++) {
                String str = s.substring(j, i);
                
                if (dp[j] && wordDict.contains(str)) {
                    dp[i] = true;
                    break;
                }
            }
        }
        
        return dp[s.length()];
    }
    
    void wordBreakHelper(String s, List<String> wordDict, List<String> result, 
        String item, int start) {
        if (start == s.length()) {
            result.add(item);
            return;
        }
        
        StringBuilder sb = new StringBuilder();
        for (int i = start; i < s.length(); i++) {
            sb.append(s.charAt(i));
            
            if (wordDict.contains(sb.toString())) {
                String newItem = "";
                
                if (item.length() > 0) {
                    newItem = item + " " + sb.toString(); 
                } else {
                    newItem = sb.toString();
                }
                
                wordBreakHelper(s, wordDict, result, newItem, i + 1);
            }
        }
    }
}

Hope this helps,
Michael