难度: 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`的子字符串是否与单词相匹配来实现此功能。每次找到匹配,就记录一个新的索引对。因此,即使单词在文本中部分重叠或多次出现,也会为每个匹配创建一个单独的索引对。
排序的目的是确保输出的索引对是按照文本中出现的顺序(即按照第一个元素的升序,如果第一个元素相同,则按照第二个元素升序)排列的,这样使结果更加有序且易于验证。在多个单词或单个单词多次出现时,不同的开始索引可能会在不同的迭代中被添加到结果列表中,这可能导致最终的索引对列表是无序的。如果题目或使用者需要有序的输出结果,这个排序步骤是必要的。