经典动态规划：分割类问题-03（LC139）

题目：给定一个字符串和一个字符串集合，求是否存在一种分割方式，使得原字符串分割后的子字
符串都可以在集合内找到。

题解：类似于完全平方数分割问题，这道题的分割条件由集合内的字符串决定，因此在考虑每个分
割位置时，需要遍历字符串集合，以确定当前位置是否可以成功分割。注意对于位置 0，需要初
始化值为真。

对于检查一个字符串是否出现在给定的字符串列表里一般可以考虑哈希表来快速判断，同时也可以做一些简单的剪枝，枚举分割点的时候倒着枚举，如果分割点 j 到 ii的长度已经大于字典列表里最长的单词的长度，那么就结束枚举，但是需要注意的是下面的代码给出的是不带剪枝的写法。

优化一下，dp[i]只需要往前探索到词典里最长的单词即可，优化后击败100%

class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
    int len =s.length(),maxw=0;
    boolean[]dp=new boolean[len+1];
    dp[0]=true;
    Set<String>set=new HashSet();
    for(String str:wordDict){
        set.add(str);
        maxw=Math.max(maxw,str.length());
    }
    for(int i=1;i<len+1;i++){
        for(int j=i;j>=0&&j>=i-maxw;j--){
            if(dp[j]&&set.contains(s.substring(j,i))){
                dp[i]=true;
                break;
            }
        }
    }
    return dp[len];
    }
}