image.png

解法

class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        int len = s.length();
        Set<String> wordSet = new HashSet<>(wordDict); 
        // 代表长度为i的字符，到下标i-1，是否可以被wordDict拆分
        boolean dp[] = new boolean[len + 1];
        // 初始化为true,不然后面的依赖无法为true了
        dp[0] = true;
        // 先遍历容量，再遍历物品
        for (int i = 1; i <= len; i++) {
            for (int j = 0; j <= i; j++) {
                String str = s.substring(j, i);
                // 如果j到i可以被找到，且j之前也能被拆分，整体就能被拆分
                if (wordSet.contains(str) && dp[j] == true) {
                    dp[i] = true;
                }
            }
        }
        return dp[len];
    }
}