0

What is the time and space complexity of the following code to search a string inside other string, on finding, function should return the index of first occurrence,else -1.

I assume time complexity is O(m*n) where m is length of haystack and n is length of needle.

However, i searched for the the memory complexity of python slice and found this answer here - Time complexity of string slice , according to it it is O(n^2).

So what is the overall time and space complexity of the below function.

Can we improve it by using memoryview on haystack.?

class Solution:
  def strStr(self, haystack, needle):
    if haystack == needle or needle == "":
        return 0
    
    needle_len = len(needle)
    haystack_len = len(haystack)
    
    for i in range(0, haystack_len - needle_len + 1):
        if needle == haystack[i:i+needle_len]:
            return i
    
    return -1
Codeformer
  • 2,060
  • 9
  • 28
  • 46
  • 1
    Even if string silces were O(1) or if you had turned the strings into lists before checking them, you are doing an `O(n)` comparison inside an `O(n)` loop. Your code would still be `O(n^2)` (more generally `O(M*N)` where M is the length of needle, N is the length of haystack) – rdas Jun 20 '21 at 11:04
  • Any reason you don't use [`.index`](https://stackoverflow.com/questions/36868479/python-str-index-time-complexity)? It has better time complexity, also used by [in](https://stackoverflow.com/questions/18139660/python-string-in-operator-implementation-algorithm-and-time-complexity) – trincot Jun 20 '21 at 11:15
  • @trincot Just practicing. – Codeformer Jun 20 '21 at 12:31
  • It seems you ask 2 questions: what is complexity, how can we improve? Should be one question only. – trincot Jun 20 '21 at 12:36

0 Answers0