Java编写:给定一个非空字符串 s 和一个包含非空单词的列表 wordDict,判定 s 是否可以被空格拆分为一个或多个在字典中出现的单词。
时间: 2024-10-12 16:06:58 浏览: 32
在Java中,你可以通过遍历字典中的每个单词,并检查它们是否是字符串s的一个连续子串来解决这个问题。这里是一个简单的算法步骤:
1. 创建一个布尔变量`canFormSentence`并初始化为`false`,用于记录字符串`s`是否能被分割成字典中的单词。
2. 定义两个指针`start`和`end`,分别表示当前查找开始和结束的位置,初始都设为0。
3. 遍历字典`wordDict`中的每个单词`word`:
a. 使用`String`的`indexOf`方法从`s`的开头开始查找`word`,如果找到并且从`start`到`end`的长度等于`word`的长度,则更新`canFormSentence`为`true`,因为找到了一个完整的单词匹配。
b. 如果找到`word`,则将`end`设置为下一个单词的起始位置加`word.length()`,继续查找下一个单词。
4. 如果遍历完所有单词仍然没有找到完整匹配,但是`s`剩余部分为空(即`end == s.length()`),说明`s`是以某个单词结尾的部分,这可能也是一个匹配的情况,所以此时也更新`canFormSentence`为`true`。
5. 遍历结束后,返回`canFormSentence`,它表示`s`是否可以由字典中的单词组成。
```java
List<String> wordDict = Arrays.asList("hello", "world", "leetcode");
String s = "helloworld";
boolean canFormSentence = false;
int start = 0, end = 0;
for (String word : wordDict) {
int index = s.indexOf(word, start);
if (index != -1) {
// 如果找到完整的单词
if (index == start && index + word.length() == end) {
canFormSentence = true;
} else {
// 更新start和end位置继续查找
start = index + word.length();
}
}
}
// 检查s剩余部分是否单独构成一个词
if (end == s.length()) {
canFormSentence = true;
}
System.out.println(canFormSentence); // 输出结果
阅读全文