动态规划子数组系列一＞单词拆分

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

       //优化⼀：将字典里面的单词放入哈希表，为后续找字串提高速度
       Set<String> hash = new HashSet<>(wordDict);

       int n = s.length();
       boolean[] dp = new boolean[n+1];
       dp[0] = true;
       s = " "+ s;//处理下标映射
       for(int i = 1; i <= n; i++)
           for(int j = i; j >= 1; j--){
               if(dp[j-1] && hash.contains(s.substring(j,i+1))){
                   dp[i] = true;
                   break;//优化二：找到一个拼接成功可以跳出
                }
            }

        return dp[n];
    }