Неизменные строки Python? Временная сложность при индексации? - PullRequest
Новая
       7

Неизменные строки Python? Временная сложность при индексации?

1 голос
/ 23 января 2020

Я пытаюсь решить вопрос программирования. 

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) сложность времени .

Однако я запутался в 7-й строке, где я пишу w = "".join(text[l:r]). Будет ли это рассматриваться как операция O (n) как индексирование массива (операция O (1)), а затем копирование его в строковую (операция O (n))?

Итак, действительно ли этот код O ( n ^ 3)?

Большое спасибо за любые советы.

1 Ответ

4 голосов
/ 23 января 2020

Несмотря на сходство синтаксиса, text[l:r] - это операция среза, а не операция индексации. Индексирование равно O (1), потому что вы ищете и возвращаете один из n элементов. Здесь, однако, срез возвращает O (n) из n элементов, так что это операция O (n), что приводит к времени выполнения O (n ** 3) для функции в целом .

...