Find the Index of the First Occurrence in a String

The problem

Given two strings needle and haystack, return the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack.

Function: def strStr(haystack,needle):

Example input (a JSON list of arguments): ["sadbutsad", "sad"]
Expected output: 0

Inputs satisfy the problem statement. Sequences contain at most 200 elements unless a smaller bound is stated. Use JSON values and the supplied function signature.

Hints

1. Check each candidate start and compare the whole needle.
2. Check the supplied examples, empty/boundary cases and the stated answer policy before optimizing.

Worked answer

Try it yourself first. When you are ready, open the answer below.

def strStr(haystack,needle):
    for i in range(len(haystack)-len(needle)+1):
        if haystack[i:i+len(needle)]==needle: return i
    return -1

Why it works

Check each candidate start and compare the whole needle. The empty needle occurs at index zero. This direct search states its O(mn) worst case rather than claiming a linear string-matching algorithm.

Complexity: O(mn) time / O(n) slice space.

Time: O(mn) time · Space: O(n) slice space