https://leetcode-cn.com/problems/word-break/

这道题是要你判断能不能分解，我们给它扩展一下，求分解的方法数

动态规划

 // 深度优先
// s[0......index-1]这一段，已经分解过了，不用在操心
    // s[index.....] 这一段字符串，能够被分解的方法数，返回
public boolean wordBreak(String s, List<String> wordDict) {
    return dfs(s, 0, new HashSet<>(wordDict)) != 0;
}
public  int dfs(String s, int index, HashSet<String> wordDict) {
    if (index == s.length()) {
        return 1;
    }
    int ways = 0;
    for (int end = index; end < s.length(); end++) {
        if (wordDict.contains(s.substring(index, end + 1))) {
            ways += dfs(s, end + 1, wordDict);
        }
    }
    return ways;
}

    // 动态规划
public boolean wordBreak2(String s, List<String> wordDict) {
    Set<String> set = new HashSet<>(wordDict);
    int N = s.length();
    int[] dp = new int[N + 1];
    dp[N] = 1;
    for (int index = N - 1; index >= 0; index--) {
        int ways = 0;
        for (int end = index; end < N; end++) {
            if (set.contains(s.substring(index, end + 1))) {
                ways += dp[end + 1];
            }
        }
        dp[index] = ways;
    }
    return dp[0] != 0;
}

时间复杂度O(N^3)

优化

最里面的枚举怎么优化？（去hashset里查，样本量不大的情况看成是O(1), 样本量过大的话就是O(N)）

构建前缀树

因此现在我每次验证都是O（1）的，
然后前缀树还能帮我们剪枝， 没路了就可以break掉