1. Word Break

Given anon-emptystringsand a dictionarywordDictcontaining a list ofnon-emptywords, determine ifscan be segmented into a space-separated sequence of one or more dictionary words. You may assume the dictionary does not contain duplicate 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> wordDict) {

        if(s.length() == 0) return true;

        int n = s.length();
        boolean[] dp = new boolean[n + 1];

        dp[0] = true;
        for(int j = 0; j <= n; j ++){
            for(int i = 0; i < j; i ++){
                if(dp[i] && wordDict.contains(s.substring(i, j))){
                    dp[j] = true;
                    break;
                }
            }
        }

        return dp[n];
    }
}

2. Word Break II

Given anon-emptystringsand a dictionarywordDictcontaining a list ofnon-emptywords, add spaces insto 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"].

Note: DFS easy to TLE, take much care. use possible to optimize dfs solution!

public class Solution {


    boolean[] possible;

    public List<String> wordBreak(String s, List<String> wordDict) {

        int n = s.length();
        List<String> ans = new ArrayList<>();
        if(n == 0) return ans;

        possible = new boolean[n + 1];
        Arrays.fill(possible, true);

        dfs(s, 0, "",wordDict, ans);
        return ans;
    }

    public void dfs(String s, int start, String sub, List<String> wordDict, List<String> ans) {

        if(start == s.length()){
            ans.add(sub.substring(1));
            return;
        }

        for(int i = start + 1; i <= s.length(); i ++){
            String word = s.substring(start, i);
            if(wordDict.contains(word) && possible[i]){

                int oldSize = ans.size();
                dfs(s, i, sub + " " + word, wordDict, ans);
                if(ans.size() == oldSize) possible[i] = false;

            }
        }
    }
}