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

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param s string字符串
     * @param wordDict string字符串一维数组
     * @return bool布尔型
     */
    public boolean wordBreak (String s, String[] wordDict) {
        // write code here
        Set<String> set = new HashSet<>(Arrays.asList(wordDict));
        int n = s.length();
        boolean[] dp = new boolean[n + 1];
        dp[0] = true;

        for (int i = 1; i <= n; i++) {
            for (int j = 0; j < i; j++) {
                if (set.contains(s.substring(j, i))) {
                    dp[i] = dp[j];
                    if (dp[i]) {
                        break;
                    }
                }
            }
        }

        return dp[n];
    }
}

Java编程语言。

该题考察的知识点是动态规划。

将字符串列表wordDict中的单词添加到集合中。然后，初始化一个boolean数组dp，dp[i]表示字符串s的前i个字符是否可以被拆分成符合要求的字符串。将dp[0]设置为true，表示空字符串可以被拆分。接下来，通过两重循环遍历字符串s的所有可能子串。对于每个子串s.substring(j, i)，如果它在集合set中存在，并且dp[j]为true（即前j个字符可以被拆分），则将dp[i]设置为true，并立即跳出内层循环。最后，返回dp[n]作为结果，其中n是字符串s的长度。