139. 单词拆分

刷题刷题找工作找工作，冲啊！

题目链接

. - 力扣（LeetCode）

自己的思路

 我没感觉这个跟动态规划有啥关系啊。

可以先用数组arr统计s单词里各个字母出现的情况，初始值都为-1，如果出现在相应下表数据写1.

接着遍历题目给出的workDist， 如果出现s里出现过的字母，将数据变0.

最后再遍历一下数组arr， 如果存在数据为1 的位置，说明是false;

动态规划思路

看了一下，发现我的理解有问题，这个题目是让workDist的完整单词能拼成字符串s，不能拆的，我理解错了。

有几个注意的点已经写在代码了。

class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        //这里给的wordDict本来就List集合不是分散的数据数据类型，所以不需要Array.asList()转换成List类型
        Set<String> set = new HashSet(wordDict);

        //这个格式跟int数组是一样的，只不过类型变成Boolean
        boolean[] dp = new boolean[s.length() + 1];
        dp[0] = true;//dp[0]不放字母
        for(int i = 1; i <= s.length();  i ++){
            for(int j = 0 ; j < i ; j ++){
                //这里要从0开始而不是1始
                //因为从0开始其实就是在说现在的字符串s[0··i-1]是否是包含在hashSet里面
                //如果从1开始就略过了这种情况
                if(dp[j] && set.contains(s.substring(j,i))){//subString可以理解为符号[)，右边不包
                    dp[i] = true;//存在，不是1，而是true
                    break;//只要这个s[0··i]存在可以拼接的字符就可以了，找到就进入下一个i
                }
            }
        }
        return dp[s.length()];
    }
}

这个题还是收获了很多，继续加油！