139. Word Break

Given a string s and a dictionary of strings wordDict, return true if s can be segmented into a space-separated sequence of one or more dictionary words.

Note that the same word in the dictionary may be reused multiple times in the segmentation.

动态规划，创建一个数组dp[]，长度为字符串长度+1，记录是否可以达到。
将dp[0]设置为1，表示可以达到。

从可取长度为1开始，遍历直到可取长度为字符串的长度。
用下一个遍历j将字符串分为两部分。（这里j从i-1下降到0会比从0上升到i-1更快。）
当dp[j]可以到达，且当前的哈希表中有(i-j)组成的字符串时，则dp[i]也可以到达。结束第二层循环。
继续搜索更长的字符串是否可以达到。
最后返回dp中的最后一个元素。

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