WordBreak

word break II 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.

给了string 和dictionary，看能否string完全分割成dictionary的词。

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()];
    }
}

优化：第二层循环不必从0开始，而是知道dict中word的最大值和最小值，可以优化一部分时间。

   public boolean wordBreak(String s, Set<String> wordDict) {
        int n = s.length();
        boolean[] canWordBreak = new boolean[n + 1];
        int minLength = Integer.MAX_VALUE;
        int maxLength = Integer.MIN_VALUE;
        for(String str : wordDict) {
            minLength = Math.min(minLength, str.length());
            maxLength = Math.max(maxLength, str.length());
        }
        canWordBreak[0] = true;
        for(int i = minLength; i <= n; i++) {
            for(int j = i - minLength; j >= 0 && j >= i - maxLength; j--) {
                if(canWordBreak[j] && wordDict.contains(s.substring(j, i))) {
                    canWordBreak[i] = true;
                    break;
                }
            }
        }
        return canWordBreak[n];
    }

word break II LC 140

Follow up: 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.

Using DFS directly will lead to TLE, so I just used HashMap to save the previous results to prune duplicated branches, as the following:

public class Solution {
    public List<String> wordBreak(String s, Set<String> wordDict) {
        List<String> res = new ArrayList<String>();
        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;

    }
}