使用java 给定一个非空字符串 s 和一个包含非空单词的列表 wordDict,判定 s 是否可以被空格拆分为一个或多个在字典中出现的单词的代码
时间: 2024-10-14 09:13:31 浏览: 38
在Java中,你可以通过构建一个简单的逻辑来判断给定字符串`s`是否能由`wordDict`中的单词组成。以下是一个基本的示例代码:
```java
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
public class Solution {
public boolean wordBreak(String s, List<String> wordDict) {
// 将字典转换为Set,以提高查找速度
Set<String> dictSet = new HashSet<>(wordDict);
// 使用动态规划方法,记录每个位置是否能够形成合法的单词组合
boolean[] dp = new boolean[s.length() + 1];
dp[0] = true; // 空字符串可以被看作是空词
for (int i = 1; i <= s.length(); i++) {
for (int j = i - 1; j >= 0; j--) {
if (dictSet.contains(s.substring(j, i))) { // 如果当前子串是字典中的单词
dp[i] |= dp[j]; // 更新状态,表示从当前位置开始有解
}
}
}
return dp[s.length()];
}
// 示例
public static void main(String[] args) {
Solution solution = new Solution();
List<String> wordDict = Arrays.asList("hi", "world", "lorem");
String s = "hello world";
System.out.println(solution.wordBreak(s, wordDict)); // 输出:true
}
}
```
在这个代码中,我们首先将字典转换为HashSet,然后使用动态规划的思想。dp数组的元素dp[i]表示字符串s的前i个字符是否可以用字典中的单词连接而成。我们从长度较短的子串开始遍历,如果子串是字典中的单词,则更新dp[i]的值。
阅读全文