Solving Implement strStr() in Python: Step-by-Step Guide

Introduction to Implement strStr()

The strStr() problem is one of the most fundamental string matching challenges in computer science. Originally popularized by LeetCode, it asks you to implement a function that finds the first occurrence of a substring (needle) within a larger string (haystack) and returns its starting index. If the needle is not found, the function should return -1.

This problem is essentially asking you to reimplement Python's built-in str.find() method from scratch. While Python provides this functionality natively, understanding how to implement it manually is crucial for mastering string algorithms and performing well in technical interviews.

Why This Problem Matters

You might wonder why we need to implement something that Python already does efficiently. The answer lies in what this problem teaches you about algorithmic thinking and string manipulation.

• Foundation for string algorithms: String matching is used everywhere from text editors to search engines to bioinformatics.
• Interview staple: This problem frequently appears in coding interviews at major tech companies because it tests multiple concepts simultaneously.
• Algorithm introduction: It serves as a gateway to more complex pattern matching algorithms like KMP, Boyer-Moore, and Rabin-Karp.
• Edge case handling: The problem requires careful consideration of empty strings, single characters, and strings longer than the haystack.

Understanding the Problem Statement

Before diving into solutions, let's clearly define what we need to implement. Given two strings, haystack and needle, return the index of the first occurrence of needle in haystack. If needle is an empty string, return 0. If needle is not found, return -1.

Here are some example inputs and expected outputs:

• haystack = "hello", needle = "ll" → returns 2
• haystack = "aaaaa", needle = "bba" → returns -1
• haystack = "", needle = "" → returns 0
• haystack = "abc", needle = "" → returns 0

Solution 1: Brute Force Approach

The most straightforward approach is to check every possible starting position in the haystack where the needle could begin. For each position, compare characters one by one until either a mismatch is found or the entire needle matches.

This approach has a time complexity of O(n × m) where n is the length of the haystack and m is the length of the needle. The space complexity is O(1) since we only use a few variables.

def strStr(haystack: str, needle: str) -> int:
    # Handle empty needle case
    if not needle:
        return 0
    
    n = len(haystack)
    m = len(needle)
    
    # If needle is longer than haystack, it cannot be found
    if m > n:
        return -1
    
    # Check every possible starting position
    for i in range(n - m + 1):
        # Try to match needle starting at position i
        match = True
        for j in range(m):
            if haystack[i + j] != needle[j]:
                match = False
                break
        
        if match:
            return i
    
    return -1

# Test the function
print(strStr("hello", "ll"))      # Output: 2
print(strStr("aaaaa", "bba"))     # Output: -1
print(strStr("abc", ""))          # Output: 0
print(strStr("mississippi", "issip"))  # Output: 4

The brute force solution works well for small strings and is easy to understand. However, it can be inefficient for large inputs because it may repeatedly compare characters that have already been matched.

Solution 2: Using Python Slicing

Python's string slicing provides a more elegant way to implement the brute force approach. Instead of comparing characters one by one, we can extract a substring of the same length as the needle and compare it directly.

def strStr(haystack: str, needle: str) -> int:
    if not needle:
        return 0
    
    n = len(haystack)
    m = len(needle)
    
    if m > n:
        return -1
    
    for i in range(n - m + 1):
        # Compare slice of haystack with needle
        if haystack[i:i + m] == needle:
            return i
    
    return -1

# Test the function
print(strStr("hello", "ll"))   # Output: 2
print(strStr("world", "or"))   # Output: 1
print(strStr("python", "th"))  # Output: 2

This version is more Pythonic and easier to read. While the theoretical time complexity remains O(n × m), Python's built-in string comparison is implemented in C and is significantly faster than manual character-by-character comparison in pure Python.

Solution 3: Using Python's Built-in find()

In a real-world scenario, the most practical solution is to use Python's built-in find() method. This is what you should use in production code unless you have specific reasons to implement your own.

def strStr(haystack: str, needle: str) -> int:
    return haystack.find(needle)

# Test the function
print(strStr("hello", "ll"))      # Output: 2
print(strStr("aaaaa", "bba"))     # Output: -1
print(strStr("abc", ""))          # Output: 0
print(strStr("", ""))             # Output: 0

The find() method handles all edge cases automatically, including empty strings, and returns -1 when the substring is not found. It is also highly optimized at the C level, making it the fastest option in practice.

Solution 4: KMP Algorithm

For large inputs, the Knuth-Morris-Pratt (KMP) algorithm offers better performance with a time complexity of O(n + m). The key insight behind KMP is that when a mismatch occurs, we can use information about previously matched characters to skip unnecessary comparisons.

KMP works by precomputing a partial match table (also called the failure function or LPS array) that tells us how far to shift the needle when a mismatch occurs. This avoids re-examining characters that we already know will match.

def strStr(haystack: str, needle: str) -> int:
    if not needle:
        return 0
    
    # Build the LPS (Longest Proper Prefix which is also Suffix) array
    def buildLPS(pattern: str) -> list:
        m = len(pattern)
        lps = [0] * m
        length = 0  # Length of the previous longest prefix suffix
        i = 1
        
        while i < m:
            if pattern[i] == pattern[length]:
                length += 1
                lps[i] = length
                i += 1
            else:
                if length != 0:
                    length = lps[length - 1]
                else:
                    lps[i] = 0
                    i += 1
        
        return lps
    
    n = len(haystack)
    m = len(needle)
    
    if m > n:
        return -1
    
    lps = buildLPS(needle)
    
    i = 0  # Index for haystack
    j = 0  # Index for needle
    
    while i < n:
        if haystack[i] == needle[j]:
            i += 1
            j += 1
            
            if j == m:
                return i - j  # Found the needle
        else:
            if j != 0:
                j = lps[j - 1]
            else:
                i += 1
    
    return -1

# Test the function
print(strStr("ABABDABACDABABCABAB", "ABABCABAB"))  # Output: 10
print(strStr("hello", "ll"))                        # Output: 2
print(strStr("mississippi", "issip"))               # Output: 4

The KMP algorithm is more complex but significantly more efficient for large strings with repetitive patterns. The LPS array construction takes O(m) time, and the search phase takes O(n) time, giving us a total time complexity of O(n + m).

Solution 5: Rabin-Karp Algorithm

The Rabin-Karp algorithm uses hashing to find the needle in the haystack. Instead of comparing characters directly, it compares hash values. When hash values match, it then verifies the actual characters to avoid false positives due to hash collisions.

def strStr(haystack: str, needle: str) -> int:
    if not needle:
        return 0
    
    n = len(haystack)
    m = len(needle)
    
    if m > n:
        return -1
    
    # Use a large prime for hashing to reduce collisions
    base = 256
    prime = 101
    
    # Calculate hash of needle and first window of haystack
    needle_hash = 0
    haystack_hash = 0
    h = 1  # The value of base^(m-1)
    
    for i in range(m - 1):
        h = (h * base) % prime
    
    for i in range(m):
        needle_hash = (base * needle_hash + ord(needle[i])) % prime
        haystack_hash = (base * haystack_hash + ord(haystack[i])) % prime
    
    # Slide the pattern over the text
    for i in range(n - m + 1):
        # If hash values match, check characters
        if needle_hash == haystack_hash:
            # Verify character by character
            match = True
            for j in range(m):
                if haystack[i + j] != needle[j]:
                    match = False
                    break
            if match:
                return i
        
        # Calculate hash for next window
        if i < n - m:
            haystack_hash = (base * (haystack_hash - ord(haystack[i]) * h) + 
                            ord(haystack[i + m])) % prime
            
            # Handle negative hash values
            if haystack_hash < 0:
                haystack_hash += prime
    
    return -1

# Test the function
print(strStr("hello", "ll"))      # Output: 2
print(strStr("world", "ld"))      # Output: 3
print(strStr("aaaaa", "bba"))     # Output: -1

Rabin-Karp has an average time complexity of O(n + m) but can degrade to O(n × m) in the worst case due to hash collisions. It is particularly useful when searching for multiple patterns simultaneously, as you can compute hashes for all patterns and compare them in a single pass.

Comparing the Solutions

Each solution has its own trade-offs. Here is a summary to help you choose the right approach for different situations:

• Brute Force: Simple to implement and understand. Best for small strings or when code clarity is more important than performance.
• Python Slicing: More Pythonic version of brute force. Leverages C-level optimizations for string comparison.
• Built-in find(): The best choice for production code. Highly optimized and handles all edge cases.
• KMP Algorithm: Optimal for large strings with repetitive patterns. O(n + m) time complexity makes it efficient for big inputs.
• Rabin-Karp: Good for multiple pattern matching. Uses hashing which can be extended to search multiple needles simultaneously.

Best Practices

When implementing strStr() or any string matching algorithm, keep these best practices in mind:

• Always handle edge cases first: Empty strings, needle longer than haystack, and single-character strings should be checked before the main logic.
• Choose the right algorithm for your use case: Do not over-engineer simple problems. If the built-in method works, use it.
• Test thoroughly: Include test cases for edge cases like empty strings, no match found, match at the beginning, match at the end, and overlapping patterns.
• Consider memory usage: Some algorithms use additional memory for preprocessing. Make sure this is acceptable for your constraints.
• Profile before optimizing: Only use complex algorithms like KMP or Rabin-Karp when profiling shows that the brute force approach is a bottleneck.

Common Pitfalls to Avoid

When solving this problem, developers often make several common mistakes. Being aware of these can save you debugging time:

• Off-by-one errors: The loop should run from 0 to n - m inclusive, not n - m - 1. Using range(n - m + 1) ensures you check the last valid starting position.
• Forgetting the empty needle case: An empty needle should return 0, not -1. This is a common edge case that interviewers test.
• Not checking if needle is longer than haystack: If the needle is longer than the haystack, it is impossible to find a match. Return -1 early to avoid unnecessary computation.
• Index out of bounds: When comparing characters, make sure your indices stay within valid bounds. This is especially important in the brute force approach.

Testing Your Implementation

A robust test suite is essential for verifying your implementation. Here is a comprehensive set of test cases you should include:

def test_strStr(strStr_func):
    # Basic cases
    assert strStr_func("hello", "ll") == 2
    assert strStr_func("world", "rl") == 2
    assert strStr_func("python", "th") == 2
    
    # Needle not found
    assert strStr_func("aaaaa", "bba") == -1
    assert strStr_func("abc", "d") == -1
    
    # Empty needle
    assert strStr_func("abc", "") == 0
    assert strStr_func("", "") == 0
    
    # Empty haystack, non-empty needle
    assert strStr_func("", "a") == -1
    
    # Needle equals haystack
    assert strStr_func("abc", "abc") == 0
    
    # Needle longer than haystack
    assert strStr_func("ab", "abc") == -1
    
    # Match at the beginning
    assert strStr_func("abcdef", "abc") == 0
    
    # Match at the end
    assert strStr_func("abcdef", "def") == 3
    
    # Overlapping patterns
    assert strStr_func("mississippi", "issip") == 4
    assert strStr_func("abababab", "abab") == 0
    
    # Single character cases
    assert strStr_func("a", "a") == 0
    assert strStr_func("a", "b") == -1
    
    print("All tests passed!")

# Run tests with any of our implementations
test_strStr(strStr)

Running these tests against your implementation will help ensure correctness across a wide range of scenarios. This is especially important if you are preparing for coding interviews where edge cases are heavily tested.

Conclusion

Implementing strStr() is an excellent exercise that teaches fundamental string matching concepts. While the brute force approach is sufficient for most practical purposes and Python's built-in find() method is the best choice for production code, understanding advanced algorithms like KMP and Rabin-Karp expands your algorithmic toolkit and prepares you for more complex string processing challenges. The key is to understand the trade-offs between simplicity and efficiency, and to choose the right approach based on your specific requirements. Whether you are preparing for an interview or building a text processing application, mastering these techniques will make you a more versatile and effective developer.