leetcode
leetcode 951 ~ 1000
字符串的索引对

字符串的索引对

难度:

标签:

题目描述

代码结果

运行时间: 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`?
这个循环条件确保了当我们在文本`text`中查找单词`v`时不会超出`text`的范围。因为我们需要检查的是从索引`i`开始的长度为`n`的子字符串,所以最大的起始索引`i`应该是`m - n`,这样从`i`到`i + n - 1`的子字符串正好是长度为`n`,并且不会超过文本的总长度。如果`i`大于`m - n`,那么`i + n - 1`将超出字符串的边界,导致索引错误。
🦆
此算法在遇到重叠或多次出现的单词时是如何处理的?例如,单词在文本中重叠出现时,会有多个索引对吗?
是的,如果单词在文本中重叠或多次出现,算法会为每次出现记录一个索引对。该算法通过遍历文本中的每个可能起始位置,并检查从该位置开始的长度为`n`的子字符串是否与单词相匹配来实现此功能。每次找到匹配,就记录一个新的索引对。因此,即使单词在文本中部分重叠或多次出现,也会为每个匹配创建一个单独的索引对。
🦆
在实现中使用了`ans.sort()`对结果进行排序,排序的目的是什么?在什么情况下,这个排序是必要的?
排序的目的是确保输出的索引对是按照文本中出现的顺序(即按照第一个元素的升序,如果第一个元素相同,则按照第二个元素升序)排列的,这样使结果更加有序且易于验证。在多个单词或单个单词多次出现时,不同的开始索引可能会在不同的迭代中被添加到结果列表中,这可能导致最终的索引对列表是无序的。如果题目或使用者需要有序的输出结果,这个排序步骤是必要的。

相关问题