字符串的索引对
难度:
标签:
题目描述
代码结果
运行时间: 28 ms, 内存: 16.9 MB
// 题目思路: 我们可以利用Java Stream来简化代码,通过遍历查询词,用字符串的indexOf方法来查找每个查询词在字符串中的位置。
// 每找到一个我们就将其起始和结束索引加入结果列表,并用stream流式处理返回结果。
import java.util.*;
import java.util.stream.*;
public class Solution {
public int[][] indexPairs(String text, String[] words) {
return Arrays.stream(words)
.flatMap(word -> {
List<int[]> indices = new ArrayList<>();
int index = text.indexOf(word);
while (index != -1) {
indices.add(new int[]{index, index + word.length() - 1});
index = text.indexOf(word, index + 1);
}
return indices.stream();
})
.toArray(int[][]::new);
}
}
解释
方法:
此题解使用了直接的字符串匹配方法来解决问题。首先,它定义一个空列表ans用于存储答案。然后,遍历每一个单词v。对于每个单词v,从文本字符串text中寻找所有的匹配项。具体实现为,遍历text中的每个可能的起始位置i(从0到m-n,m是text的长度,n是单词v的长度)。在每个位置i,检查从i开始长度为n的子字符串是否与单词v相等。如果相等,则将[i, i+n-1]作为匹配的索引对添加到答案列表中。所有单词检查完毕后,对答案列表进行排序,以便输出有序的索引对。
时间复杂度:
O(k * m * n)
空间复杂度:
O(k * m)
代码细节讲解
🦆
在解题方法中,对于文本长度m和单词长度n的处理,为什么循环的条件是`i <= m - n`?
▷🦆
此算法在遇到重叠或多次出现的单词时是如何处理的?例如,单词在文本中重叠出现时,会有多个索引对吗?
▷🦆
在实现中使用了`ans.sort()`对结果进行排序,排序的目的是什么?在什么情况下,这个排序是必要的?
▷