139. Word Break I and II

https://leetcode.com/problems/word-break/description/

解题思路：用动态规划，看字典是否包含s的某一段
关键解法是：dp[j] && wordDict.contains(s.substring(j,i)

代码：
class Solution {
public boolean wordBreak(String s, List<String> wordDict) {

    int len = s.length();
    boolean[] dp = new boolean[len + 1];
    dp[0] = true;
    for (int i = 1; i <= len; i++){
        for(int j = 0; j < i; j++){
            if(dp[j] && wordDict.contains(s.substring(j,i))){
                dp[i] = true;
                break;
            }
        }
    }
    return dp[len];
}

}

https://leetcode.com/problems/word-break-ii/description/
解题思路：用深搜而且还会为map

代码：

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

    return DFS(s, wordDict, new HashMap<String, List<String>>());
}

public List<String> DFS(String s, List<String> wordDict, HashMap<String, List<String>> map){
    if(map.containsKey(s)){
        return map.get(s);
    }
    List<String> list = new ArrayList<String>();
    if(s.length() == 0){
        list.add("");
    }
    for(String word : wordDict){
        if(s.startsWith(word)){
            List<String> subString = DFS(s.substring(word.length()), wordDict, map);
            for(String sub : subString){
                list.add(word + (sub.isEmpty() ? "" : " ") + sub);
            }
        }
    }
    map.put(s, list);
    return list;
}

}