单词拆分

这道题.....不会做，看了答案，动态规划真timo的简单，不过动态转移方程得想出来啊????

重点：

// dp[i] 代表前i个数能否被拆分，满足要求
// 动态转移方程 dp[i] = (dp[j] && [j~i]是个单词)

import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Set;

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

        // 动态规划 最优子结构、重叠子问题、动态转移方程

        // dp[i] 代表前i个数能否被拆分
        // 动态转移方程 dp[i] = (dp[j] && [j~i]是个单词)
        Boolean []dp = new Boolean[s.length()+1];
        for(int i=0; i<dp.length; i++){
            dp[i] = false;
        }

        // 空是为true
        dp[0] = true;

        // 判断字符串是否出现过
        Set<String> set = new HashSet<>();
        for(String word: wordDict){
            set.add(word);
        }

        // 遍历
        for(int i=0; i<=s.length(); i++){
            for(int j=0; j<i; j++){
                String data = s.substring(j, i);
                if(dp[j] && set.contains(data)){
                    dp[i] = true;
                }
            }
        }

        return dp[s.length()];
    }

    public static void main(String[] args) {
        Solution s = new Solution();
        List<String> ls = new LinkedList<>();
        ls.add("leete");
        ls.add("code");
        s.wordBreak("leetecode", ls);
    }
}