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
        HashSet<String> set = new HashSet<>();
        for (String word : wordDict) {
            StringBuilder sb = new StringBuilder(word);
            sb.reverse();
            set.add(sb.toString());
        }

        int n = s.length();
        boolean[] dp = new boolean[n + 1];
        dp[0] = true;
        for (int i = 1; i <= n; i++) {
            StringBuilder cur = new StringBuilder();
            for (int j = i - 1; j >= 0; j--) {
                cur.append(s.charAt(j));
                if (set.contains(cur.toString())) {
                    dp[i] = dp[i] || dp[j];
                }
                if (dp[i] || cur.length() > 25) {
                    break;
                }
            }
        }
        return dp[n];
    }
}

编程语言是Java。

该题考察的知识点是动态规划和字符串处理。

代码简短的文字解释如下：

1. 将wordDict中的单词逆序，并存储在HashSet集合set中。这样可以方便地检查一个字符串的逆序是否存在于wordDict中。
2. 创建一个长度为n+1的布尔数组dp，其中dp[i]表示从字符串s的前i个字符能否被分割成由wordDict中的单词组成的句子。
3. 初始化dp[0]为true，表示空字符串可以被分割。
4. 遍历字符串s，从第一个字符开始到最后一个字符：对于当前位置i，构建一个空的StringBuilder对象cur来记录从s的第i-1个字符开始往前的部分字符。从i-1往前遍历，将字符添加到cur中，并检查cur的逆序是否存在于set中。如果存在，则说明从s的第j个字符（j从i-1到0循环）到第i个字符可以被分割，此时将dp[i]标记为true。如果不存在，并且当前逆序字符串的长度超过25，说明无法继续匹配更长的字符串，跳出循环。
5. 最后返回dp[n]，即表示整个字符串s是否能够被分割成由wordDict中的单词组成的句子。