本文共 1213 字，大约阅读时间需要 4 分钟。
要解决这个问题，我们可以使用动态规划的方法。这个方法通过定义一个状态数组来跟踪字符串是否可以拆分成符合要求的单词组合。具体来说，定义 dp[i] 表示前 i 个字符组成的字符串 s[0...i-1] 是否可以被空格拆分成一个或多个在字典中出现的单词。
dp，其中 dp[i] 表示前 i 个字符是否可以拆分成符合要求的单词组合。初始化 dp[0] 为 true，表示空字符串合法。s，对于每个位置 i，检查所有可能的分割点 j。如果 dp[j] 为 true 且 s[j...i-1] 在字典中，则 dp[i] 设为 true。import java.util.HashSet;import java.util.List;import java.util.Set;public class Solution { public boolean wordBreak(String s, List wordDict) { Set dictSet = new HashSet<>(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 (dp[j] && dictSet.contains(s.substring(j, i))) { dp[i] = true; break; } } } return dp[n]; }} dictSet 中，以便快速查找。dp 数组的长度为 s.length() + 1，dp[0] 初始化为 true。i，遍历所有可能的分割点 j。如果 dp[j] 为 true 且 s[j...i-1] 在集合中，则 dp[i] 设为 true 并跳出循环。dp[n]，即最后一个位置是否为 true，表示整个字符串是否可以被拆分成符合要求的单词组合。这种方法的时间复杂度为 O(n^2)，空间复杂度为 O(n)，适用于处理较短的字符串。
转载地址：http://zhbn.baihongyu.com/