Word Break II

Word Break II

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

Solution

check before constructing the sentences.

Code

public class Solution {
    public List<String> wordBreak(String s, Set<String> dict) {
        List<String> res = new ArrayList<String>();
        int n = s.length();
        boolean[] canBreak = new boolean[n+1];
        canBreak[n] = true;
        for (int i = n - 1; i >= 0; --i) {
            for (int j = i; j < n; ++j) {
                if (dict.contains(s.substring(i,j+1)) && canBreak[j+1]) {
                    canBreak[i] = true;
                    break;
                }
            }
        }
        if (canBreak[0] == false) return res;
        wordBreakRe(s, dict, "", 0, res);
        return res;
    }
    public void wordBreakRe(String s, Set<String> dict, String path, int start, List<String> res) {
        if (start == s.length()) {
            res.add(path);
            return;
        }
        if (path.length() != 0) path = path + " ";
        for (int i = start; i < s.length(); ++i) {
            String word = s.substring(start, i + 1);
            if (dict.contains(word) == false) continue;
            wordBreakRe(s, dict, path + word, i + 1, res);
        }
    }
}