NUHMAN.com

Introduction

LeetCode 28: Implement strStr() (also known as indexOf) asks you to find the first occurrence of a substring (needle) in another string (haystack). If the substring is not found, return -1.

This classic string problem introduces you to both the brute-force search and the more efficient KMP algorithm.

Problem Statement

Implement the strStr() function.

Return:

• The index of the first occurrence of needle in haystack, or
• -1 if needle is not part of haystack.

Examples

go

Input: haystack = "hello", needle = "ll"
Output: 2
go

Input: haystack = "aaaaa", needle = "bba"
Output: -1
go

Input: haystack = "", needle = ""
Output: 0

Approach 1: Brute Force

Check all substrings of length equal to needle in haystack.

Go Implementation

go

func strStr(haystack string, needle string) int {
    n, m := len(haystack), len(needle)
    if m == 0 {
        return 0
    }

    for i := 0; i <= n-m; i++ {
        if haystack[i:i+m] == needle {
            return i
        }
    }
    return -1
}

Approach 2: KMP Algorithm (Knuth-Morris-Pratt)

• Preprocess the needle to build a longest prefix-suffix (LPS) array.
• Use the LPS array to avoid re-checking matched characters.

KMP Go Implementation

go

func strStr(haystack string, needle string) int {
    if len(needle) == 0 {
        return 0
    }

    lps := computeLPS(needle)
    i, j := 0, 0

    for i < len(haystack) {
        if haystack[i] == needle[j] {
            i++
            j++
            if j == len(needle) {
                return i - j
            }
        } else {
            if j != 0 {
                j = lps[j-1]
            } else {
                i++
            }
        }
    }

    return -1
}

func computeLPS(pattern string) []int {
    lps := make([]int, len(pattern))
    length := 0
    i := 1

    for i < len(pattern) {
        if pattern[i] == pattern[length] {
            length++
            lps[i] = length
            i++
        } else {
            if length != 0 {
                length = lps[length-1]
            } else {
                lps[i] = 0
                i++
            }
        }
    }
    return lps
}

Time and Space Complexity

ApproachTime ComplexitySpace ComplexityBrute ForceO(n * m)O(1)KMPO(n + m)O(m)

• n: Length of haystack
• m: Length of needle

Key Takeaways

• Use brute force for short strings and quick implementation.
• Use KMP for efficient searching in long strings.
• Understanding strStr() helps with deeper pattern matching problems like wildcards, regex, and substring with constraints.