LeetCode【100】单词拆分

题目：

代码：

    public boolean wordBreak(String s, List<String> wordDict) {
        Set<String> dictSet = new HashSet<>(wordDict);

        boolean[] dp = new boolean[s.length() + 1];  // dp问题均是，先构造dp数组，大小为n+1
        dp[0] = true;     // dp问题，初始化第0个元素

        for (int i = 1; i < dp.length; i++) {
            for (int j = 0; j < i; j++) {
                if (dp[j] && dictSet.contains(s.substring(j, i))) {   // 注意dp的初始条件； dp j为符合条件的字符串， i-j要在单词列表里；这题如果转化下，求满足条件单词的最小个数，这里就要Math.min了
                    dp[i] = true;
                    break;
                }
            }
        }

        return dp[s.length()];
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17