我正在尝试解决编程问题。
Given a text string and words (a list of strings), return all index pairs [i, j] so that the substring text[i]...text[j] is in the list of words.
Example 1:
Input: text = "thestoryofleetcodeandme", words = ["story","fleet","leetcode"]
Output: [[3,7],[9,13],[10,17]]
Example 2:
Input: text = "ababa", words = ["aba","ab"]
Output: [[0,1],[0,2],[2,3],[2,4]]
Explanation:
Notice that matches can overlap, see "aba" is found in [0,2] and [2,4].
我的功能是
def indexPairs(text: str, words: List[str]) -> List[List[int]]:
words = set(words) # O(w)
text = list(text) # O(n)
ans = []
for l in range(len(text)): # O(n)
for r in range(l + 1, len(text) + 1): # O(n)
w = "".join(text[l:r])
if w in words:
ans.append((l, r - 1))
return ans
我的理解是，这段代码以O（n ^ 2）的时间复杂度运行。
但是，我对写的第七行感到困惑w = "".join(text[l:r])。在索引数组（O（1）操作）然后将其复制到字符串（O（n）操作）时，是否将其视为O（n）操作？
那么，这段代码实际上是O（n ^ 3）吗？
非常感谢您的指导。
尽管语法相似，但text[l:r]它是切片操作，而不是索引操作。索引是O（1），因为你查找并返回一个对的ñ项目。不过，这里的分片返回n个项中的O（n），因此这是O（n）操作，导致整个函数的运行时间为O（n ** 3）。
本文收集自互联网，转载请注明来源。
如有侵权，请联系[email protected] 删除。
我来说两句