一个变量名为 str的字符串,一个字符串集合wordSet,请编写Java代码判断 str字符串是否可以切分为由wordSet符串集合中的单词构成的句子,单词之间用空格隔开。
时间: 2024-03-17 22:41:05 浏览: 81
好的,可以使用动态规划(DP)来解决这个问题。我们定义一个长度为 n+1 的布尔型数组 dp,dp[i] 表示 str 的前 i 个字符能否被 wordSet 中的单词分割而成。
初始时,dp[0] 为 true,表示空串可以被分割而成。
接下来,我们需要枚举分割点 j,判断 str[j:i] 是否在 wordSet 中。如果在,且 dp[j] 为 true,则 dp[i] 也为 true。最终,我们返回 dp[n] 的值即可。
下面是 Java 代码实现:
```java
public class Solution {
public boolean wordBreak(String s, List<String> 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] && wordDict.contains(s.substring(j, i))) {
dp[i] = true;
break;
}
}
}
return dp[n];
}
}
```
使用示例:
```java
List<String> wordDict = new ArrayList<>();
wordDict.add("ace");
wordDict.add("game");
String s = "acegame";
Solution solution = new Solution();
System.out.println(solution.wordBreak(s, wordDict)); // 输出 true
wordDict.clear();
wordDict.add("ace");
wordDict.add("game");
wordDict.add("love");
s = "acegamelovegame";
System.out.println(solution.wordBreak(s, wordDict)); // 输出 true
```
阅读全文