strstr implementation with python and sets

Question

Please review my strstr implementation in terms of time/space efficiency and overall readability. I am preparing for a coding assessment coming up as I am looking to pivot my career from Physics to Computer Science. This is an exercise from the interview practice questions on CodeSignal. My implementation successfully passes all 14 tests but I get the following error when I submit my answer:

Tests passed: 21/27. Execution time limit exceeded on test 22: Program exceeded the execution time limit. Make sure that it completes execution in a few seconds for any possible input.

"""strstr().

Given two strings, text and pattern, return an integer indicating the index
in the text of the first occurrence of the pattern.
"""


def strstr(text, pattern):
    """Needle in haystack O(|text|) time? and O(?) space.

    Return an integer indicating the first occurrence of pattern in the text,
    or -1 if the pattern is not part of the text.
    """
    lookup = set([pattern])
    len_text = len(text)
    len_pattern = len(pattern)
    for index in range(len_text-len_pattern+1):
        if text[index:index+len_pattern] in lookup:
            return index
    return -1


def tests():
    """Sample Tests."""
    samples = [("CodesignalIsAwesome", "IA", -1),
               ("CodesignalIsAwesome", "IsA", 10),
               ("a", "a", 0),
               ("a", "A", -1),
               ("sst", "st", 1),
               ("lrnkbldxguzgcseccinlizyogwqzlifxcthdgmanjztlt", "an", 38)]
    for text, pattern, answer in samples:
        if strstr(text, pattern) != answer:
            print(f"text: {text}, pattern: {pattern}, aswer: {answer}")


if __name__ == "__main__":
    tests()

Edit: Avoid using built-in functions to solve this challenge. Implement them yourself, since this is what you would be asked to do during a real interview.

Answer 1

As someone trying to pivot from physics to Computer Science, I think this solution is good, many CS graduates might not come up with a better solution first up.

Let's get some optimizations unrelated to cyclomatic complexity out of the way.

You added the pattern to a set. The lookup is constant O(1), I don't see a need to do that and you can save on a high constant.

Let's take a closer look at

    for index in range(len_text-len_pattern+1):
        if text[index:index+len_pattern] in lookup:

specifically text[index:index+len_pattern], this creates a copy of the string for the range index:len_pattern. This is an implementation detail of Python, one can just as easily imagine an optimization that does not create a copy.

This question and its response might help explain this better.

You might be able to optimize away the object creation, again this unrelated to cyclomatic complexity.

premature optimization is evil - the intent above is more of a code review. Addressing you question below.

---

The runtime complexity of the loop is the equivalent of creating a copy of the pattern times the len of text

if m is len(text) and n is len(pattern) the for loop is O(n*m) in every iteration.

Typically in questions like these, there is an insight that is not always obvious that drives the solution resulting in a lower cyclomatic complexity. In this instance it is that the algorithm can be implemented in a single pass O(n) by keeping track of indexes across both the text and the pattern

def strstr(text, pattern):
     
    t = 0
    len_text = len(text)
    len_pattern = len(pattern)
    i = 0
    for i in range(len_text + 1):
        if (t == len_pattern or i == len_text):
            break
        if (text[i] == pattern[t]):
            t += 1
        elif (text[i] == pattern[0]):
            t = 1
        else:
            t = 0

    if (t < len_pattern):
        return -1
    else:
        return i - t
    
def tests():
    """Sample Tests."""
    samples = [("CodesignalIsAwesome", "IA", -1),
               ("CodesignalIsAwesome", "IsA", 10),
               ("a", "a", 0),
               ("a", "A", -1),
               ("sst", "st", 1),
               ("lrnkbldxguzgcseccinlizyogwqzlifxcthdgmanjztlt", "an", 38),
               ("abcd" * 300000 + "abcde", "abcde", 1200000),]
    for text, pattern, answer in samples:
        actual = strstr(text, pattern)
        if actual != answer:
            print(f"FAILED : pattern: {pattern}, actual: {actual}, expected: {answer}")
        else:
            print(f"SUCCESS: pattern: {pattern}, actual: {actual} matched expected")

I added an additional text case to demonstrate the runtime, testing this with time module in python, the clock time of the implementation is a few milli seconds compared to the clock time of the O(n*m) algorithm which on my machine is aboue 21 seconds.