Cacher is the code snippet organizer for pro developers

/**
 * 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"].
 */
public class Solution {
    public ArrayList<String> wordBreak(String s, Set<String> dict) {
        ArrayList<String> res = new ArrayList<String>();
        if(s == null || s.length() == 0)
            return res;
        ArrayList<String> cur = new ArrayList<String>();
        int n = s.length();
        boolean[] dp = new boolean[n + 1];
        dp[0] = true;
        for(int i = 1; i <= n; i++){
            if(dict.contains(s.substring(0, i))) {
                dp[i] = true;
                continue;
            }
            for(int j = 0; j < i; j++) {
                if(dp[j] && dict.contains(s.substring(j, i))) {
                    dp[i] = true;
                }
            }
        }
        if(dp[n] == false) 
            return res; // This is all DP is about.... 
        StringBuilder cur = new StringBuilder();
        dfs(s, 0, cur, ret, dict);
        return ret;
    }
    public void dfs(String s, int start, StringBuilder cur, ArrayList<String> ret, Set<String> dict){
        int n = s.length();
        if(start >= n) {
            ret.add(new String(cur));
            return;
        }
        for(int i = start + 1; i <= n; i++) {
            String sub = s.substring(start, i);
            if(dict.contains(sub)) {
                int oldLen = cur.length();
                if(oldLen != 0)
                    cur.append(" ");
                cur.append(sub);
                dfs(s, i, cur, ret, dict);
                // backtracking. 
                cur.delete(oldLen, cur.length());
            }
        }
    }
}

/**
 * Given a string s and a dictionary of words dict, determine if s can be segmented into a space-separated sequence of one or more dictionary words.
 * For example, given
 * s = "leetcode",
 * dict = ["leet", "code"].
 * Return true because "leetcode" can be segmented as "leet code".
 */
public class Solution {
    public boolean wordBreak(String s, List<String> dict) {
        if(s == null || dict == null)
            return false;
        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++){
                if(dp[j] && dict.contains(s.substring(j, i)))
                    dp[i] = true;
            }
        }
        return dp[s.length()];
    }
}