算法练习Day46|139.单词拆分

 1class Solution {
 2    public boolean wordBreak(String s, List<String> wordDict) {
 3        // 将单词字典转换为 HashSet，以便快速查找单词是否存在
 4        HashSet<String> set = new HashSet<>(wordDict);
 5
 6        // valid 数组用于记录字符串 s 的前缀是否可以被拆分为字典中的单词
 7        boolean[] valid = new boolean[s.length() + 1];
 8        valid[0] = true; // 空字符串可以被拆分
 9
10        // 遍历字符串 s 的每个位置
11        for (int i = 1; i <= s.length(); i++) {
12            // 遍历当前位置之前的每个位置 j
13            for (int j = 0; j < i && !valid[i]; j++) {
14                // 如果子串 s[j, i] 存在于单词字典中，并且 s[0:j] 可以被拆分，则将 valid[i] 设置为true
15                if (set.contains(s.substring(j, i)) && valid[j]) {
16                    valid[i] = true;
17                }
18            }
19        }
20        // 返回 valid 数组的最后一个元素，表示整个字符串 s 是否可以被拆分为字典中的单词
21        return valid[s.length()];
22    }
23}