Problem statement

https://leetcode.com/problems/implement-strstr/

Solution

We need to find if one string is substring of another, for this problem $O(nk)$ solution is enough, however there is KMP algorighm with $O(n+k)$ complexity. Actually, function in in python will give your in average the same complexity.

Complexity

Time is $O(n+k)$, space is $O(n+k)$ as well.

Code

class Solution:
    def strStr(self, haystack, needle):
        if not needle:
            return 0
        elif needle not in haystack:
            return -1
        else:
            return len(haystack.split(needle)[0])