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

public class Solution {
    public List<String> wordBreak(String s, Set<String> wordDict) {
        if(s == null) return new ArrayList<String>();
        List<String> ans = new ArrayList<String>();
        back(s, ans, new ArrayList<String>(), wordDict);
        return ans;
    }

    public void back(String remain, List<String> ans, List<String> path, Set<String> dict) {
        if(remain.length() == 0) {
            StringBuilder sb = new StringBuilder();
            for(int i = 0; i < path.size(); i++) {
                sb.append(path.get(i));
                if(i != path.size()-1) sb.append(" ");
            }
            ans.add(sb.toString());
            return;
        }

        for(String word: dict) {
            if(remain.startsWith(word)) {
                path.add(word);
                back(remain.substring(word.length()), ans, path, dict);
                path.remove(path.size()-1);
            }
        }

        /*
        for(int i = 0; i < remain.length(); i++) {
            String sub = remain.substring(0,i+1);
            if(dict.contains(sub)) {
                path.add(sub);
                back(remain.substring(i+1), ans, path, dict);
                path.remove(path.size()-1);
            }
        }*/
    }
}