题解 | #训练聪明的牛#

知识点：动态规划 哈希表

思路：

首先，将单词字典中的每个单词进行反转，然后将反转后的单词存储在一个哈希集合 S 中。

然后，定义一个布尔型数组 f，其中 f[i] 表示前 i 个字符能否被字典中的单词拆分。初始时，将 f[0] 设置为 true，表示一个空字符串可以被拆分。

接下来，从左到右遍历字符串 s 的每个字符，计算 f[i] 的取值。对于每个 f[i]，它可以通过在之前的位置 j 处截取字符串，使得截取出的子串在字典中存在。遍历的结束条件是遍历到字符串的末尾。

在截取字符串的过程中，将截取到的子串进行反转，并判断反转后的子串是否在字典中。如果存在，那么将 f[i] 更新为 f[i] || f[j]，表示前 i 个字符能否被拆分取决于之前的某个位置 j 处的字符串是否能够被拆分。

为了优化字符串拼接的性能，使用 StringBuilder 类来进行字符串的反转和拼接操作。

最后，返回 f[n]，其中 n 是字符串 s 的长度。如果 f[n] 为 true，则表示字符串 s 可以通过字典中的单词进行拆分，否则不可拆分。

编程语言：java

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param s string字符串
     * @param wordDict string字符串一维数组
     * @return bool布尔型
     */
    public boolean wordBreak(String s, String[] wordDict) {
        Set<String> S = new HashSet<>();
        for (String ss : wordDict) {
            StringBuilder sb = new StringBuilder(ss);
            sb.reverse();
            S.add(sb.toString());
        }

        int n = s.length();
        boolean[] f = new boolean[n + 1];
        f[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 (S.contains(cur.toString())) {
                    f[i] = (f[i] || f[j]);
                }
                if (f[i] || cur.length() > 25) {
                    break;
                }
            }
        }

        return f[n];
    }
}