139. Word Break

Given a non-empty string s and a dictionary wordDict containing a list of non-empty words, determine if s can 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"

思路1：用递归和HashSet

public class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        Set<String> set = new HashSet<String>(wordDict);
        if(s == null || wordDict == null)
            return false;
        if(s.length() == 0)
            return true;
        int len = s.length();    

        for(int i = 1; i <= len; i++) {
            String frontPart = s.substring(0, i);
            String backPart = s.substring(i, len);
            if(wordDict.contains(frontPart)) {
                if(wordBreak(backPart, wordDict))
                    return true;
                wordDict.remove(frontPart);
            }
        }

        return false;
    }
}

思路2：用DP

public class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        Set<String> set = new HashSet<String>(wordDict);
        boolean[] breakable = new boolean[s.length()+1];
        breakable[0] = true;

        for(int i=1;i<=s.length();i++){
            for(int j=0;j<i;j++){
                if(breakable[j]&&dict.contains(s.substring(j,i))){
                    breakable[i] = true;
                    break;
                }
            }
        }
        return breakable[s.length()];
    }
}