Word break

lc 139

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

public class Solution {
    public boolean wordBreak(String s, Set<String> wordDict) {
        if( s == null || s.length() == 0 || wordDict == null || wordDict.size() == 0) 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] && wordDict.contains(s.substring(j, i))){
                    dp[i] = true;
                    break;
                }
            }
        }
        return dp[s.length()];
    }
}

lc140 Word Break II

public class Solution {
    public List<String> wordBreak(String s, Set<String> wordDict) {
        if(s == null || s.length() == 0 || wordDict == null || wordDict.size() == 0 ) return res;
        HashMap<String, ArrayList<String>> map = new HashMap<String, ArrayList<String>>();

        return helper(s, wordDict, map);

    }

    public List<String> helper(String s, Set<String> wordDict, HashMap<String, ArrayList<String>> map){
        ArrayList<String> res = new ArrayList<String>();
        if ( s == null || s.length() == 0 ) return res;
        if(map.containsKey(s)){
            return map.get(s);

        }
        for(int i = 0; i < s.length(); i++){
            String cur = s.substring(0, i + 1);
            //check contains cur or not?
            if(wordDict.contains(cur)){
                if( i == s.length() - 1){
                    res.add(cur);
                }else{
                    String now = s.substring( i + 1);
                    List<String> temp = helper(now, wordDict, map);

                    for(String item:temp){
                        item = cur + " " + item;
                        res.add(item);
                    }
                }
            }

        }
        map.put(s, res);
        return res;

    }
}