题解 | #训练聪明的牛# Java

定义一个布尔数组dp，其中dp[i]表示字符串s的前i个字符能否被拆分成词汇表wordDict中的单词。

首先，我们需要初始化dp数组的边界条件。将dp[0]设为true，表示空串可以被拆分成空单词。

然后，我们可以通过递推关系式来更新dp数组的其他位置。对于dp[i]，我们可以将字符串s的前i个字符拆分为两部分：s[0:i-1]和s[i:n-1]（其中n是字符串s的长度）。如果s[0:i-1]可以被拆分成词汇表wordDict中的单词，并且s[i:n-1]在wordDict中，那么dp[i]为true。即，如果存在j（0≤j<i），使得dp[j]为true并且s[j:i-1]在wordDict中，那么dp[i]为true。

最后，遍历完整个字符串s后，dp[s.length()]的值即为字符串s能否被拆分成词汇表wordDict中的单词。

import java.util.*;


public class Solution {

    public boolean wordBreak(String s, String[] wordDict) {

        boolean[] dp = new boolean[s.length() + 1];
        dp[0] = true;
        for (int i = 1; i <= s.length(); i++) {
            for (String word : wordDict) {
                int len = word.length();
                if (i >= len && s.substring(i - len, i).equals(word) && dp[i - len]) {
                    dp[i] = true;
                    break;
                }
            }
        }
        return dp[s.length()];
    }

}