力扣 139 单词拆分

题意：给定一个单词，和一个字典，判定字典中的单词能否拼接成给定的单词

思路：一维动态规划，详情见注释

思想：动态规划

复杂度：时间O（n^n)，空间O(n)

class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        int len = s.length();
        // dp[i]为true的含义是从头开始到i－1的字符串，能被字典中的单词拼接出来
        boolean[] dp = new boolean[len+1];
        // 当没有单词时，为可以拼接出来
        dp[0] = true;
        // 把单词放到hashset中方便快速查找
        HashSet<String> set = new HashSet();
        for(String str: wordDict) {
            set.add(str);
        }
        // 从头到尾遍历s
        for(int i=1;i<=len;i++) {
            // 从尾到头遍历当前子字符串0到i-2
            for(int j=i-1;j>=0;j--) {
                String temp = s.substring(j, i);
                // 当前子字符串j到i出现在字典中，而且0到j-1的字符串也能被字典拼接，那么0到i－1的字符串可以被字典拼接成子符串
                if(set.contains(temp) && dp[j]) {
                    dp[i] = true;
                    break;
                }
            }
        }
        // 返回第i－1个字符串能否被拼接
        return dp[len];
    }
}