难度: Easy
Submission
运行时间: 28 ms
内存: 16.9 MB
class Solution:
def indexPairs(self, text: str, words: List[str]) -> List[List[int]]:
ans = []
for v in words:
start, n = v[0], len(v)
m = len(text)
for i in range(0, m - n + 1):
if text[i:i+n] == v:
ans.append([i, i + n - 1])
# break
ans.sort()
return ans
Explain
此题解使用了直接的字符串匹配方法来解决问题。首先，它定义一个空列表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)
class Solution:
def indexPairs(self, text: str, words: List[str]) -> List[List[int]]:
ans = [] # 结果列表
for v in words: # 遍历每个单词
start, n = v[0], len(v) # 获取每个单词的首字母和长度
m = len(text) # 文本的长度
for i in range(0, m - n + 1): # 遍历每个可能的起始位置
if text[i:i+n] == v: # 对比位置i开始的长度为n的子字符串是否与单词v相匹配
ans.append([i, i + n - 1]) # 如果匹配，记录索引对
ans.sort() # 对结果进行排序
return ans # 返回排序后的结果
Explore
这个循环条件确保了当我们在文本`text`中查找单词`v`时不会超出`text`的范围。因为我们需要检查的是从索引`i`开始的长度为`n`的子字符串，所以最大的起始索引`i`应该是`m - n`，这样从`i`到`i + n - 1`的子字符串正好是长度为`n`，并且不会超过文本的总长度。如果`i`大于`m - n`，那么`i + n - 1`将超出字符串的边界，导致索引错误。
是的，如果单词在文本中重叠或多次出现，算法会为每次出现记录一个索引对。该算法通过遍历文本中的每个可能起始位置，并检查从该位置开始的长度为`n`的子字符串是否与单词相匹配来实现此功能。每次找到匹配，就记录一个新的索引对。因此，即使单词在文本中部分重叠或多次出现，也会为每个匹配创建一个单独的索引对。
排序的目的是确保输出的索引对是按照文本中出现的顺序（即按照第一个元素的升序，如果第一个元素相同，则按照第二个元素升序）排列的，这样使结果更加有序且易于验证。在多个单词或单个单词多次出现时，不同的开始索引可能会在不同的迭代中被添加到结果列表中，这可能导致最终的索引对列表是无序的。如果题目或使用者需要有序的输出结果，这个排序步骤是必要的。