Substring Matching Pattern

Difficulty: Easy | Acceptance: 28.70% | Paid: No Topics: String, String Matching

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

• Examples
• Constraints
• Approach 1: Built-in Methods
• Approach 2: Sliding Window (Naive)
• Approach 3: KMP Algorithm
• Approach 4: Rabin-Karp Algorithm

Examples

Example 1

Input:

s = "leetcode", p = "ee*e"

Output:

true

Explanation: By replacing the ’*’ with “tcod”, the substring “eetcode” matches the pattern.

Example 2

Input:

s = "car", p = "c*v"

Output:

false

Explanation: There is no substring matching the pattern.

Example 3

Input:

s = "luck", p = "u*"

Output:

true

Explanation: The substrings “u”, “uc”, and “uck” match the pattern.

Constraints

1 <= s.length, p.length <= 10⁴
s and p consist of only lowercase English letters.

Approach 1: Built-in Methods

Intuition Most programming languages provide optimized built-in methods to find the index of a substring within a string. We can leverage these for a concise and efficient solution.

Steps

• Check if p is empty. If so, return 0.
• Use the language’s native find/indexOf method to locate p in s.
• Return the result.

class Solution:
    def strStr(self, s: str, p: str) -> int:
        return s.find(p)

Complexity

• Time: O(n * m) in worst case, though often optimized internally.
• Space: O(1)
• Notes: Relies on standard library implementation.

Approach 2: Sliding Window (Naive)

Intuition We manually check every possible starting position in s to see if the substring starting there matches p.

Steps

• Iterate through s from index 0 to len(s) - len(p).
• For each index i, compare characters of s and p one by one.
• If all characters match, return i.
• If the loop finishes without a match, return -1.

class Solution:
    def strStr(self, s: str, p: str) -> int:
        n, m = len(s), len(p)
        for i in range(n - m + 1):
            if s[i:i+m] == p:
                return i
        return -1

Complexity

• Time: O(n * m)
• Space: O(1)
• Notes: Simple but inefficient for large strings with repeating patterns.

Approach 3: KMP Algorithm

Intuition The Knuth-Morris-Pratt algorithm optimizes the search by preprocessing the pattern p to create a Longest Prefix Suffix (LPS) array. This allows us to skip unnecessary comparisons when a mismatch occurs.

Steps

• Compute the LPS array for p. lps[i] stores the length of the longest proper prefix which is also a suffix for p[0...i].
• Traverse s with pointer i and p with pointer j.
• If characters match, increment both pointers.
• If they mismatch and j > 0, set j = lps[j-1].
• If j reaches the length of p, return the starting index i - j.

class Solution:
    def strStr(self, s: str, p: str) -> int:
        if not p: return 0
        # Compute LPS
        lps = [0] * len(p)
        length = 0
        i = 1
        while i < len(p):
            if p[i] == p[length]:
                length += 1
                lps[i] = length
                i += 1
            else:
                if length != 0:
                    length = lps[length-1]
                else:
                    lps[i] = 0
                    i += 1
        # Search
        i = 0 # index for s
        j = 0 # index for p
        while i < len(s):
            if s[i] == p[j]:
                i += 1
                j += 1
            if j == len(p):
                return i - j
            elif i < len(s) and s[i] != p[j]:
                if j != 0:
                    j = lps[j-1]
                else:
                    i += 1
        return -1

Complexity

• Time: O(n + m)
• Space: O(m)
• Notes: Linear time complexity, ideal for large inputs.

Approach 4: Rabin-Karp Algorithm

Intuition Rabin-Karp uses hashing to compare the pattern string with substrings of the text. Instead of comparing character by character, it compares hash values. If hashes match, it confirms with a direct string comparison to handle collisions.

Steps

• Calculate the hash of the pattern p.
• Calculate the hash of the first window of s (length m).
• Slide the window over s, updating the hash using a rolling hash technique.
• If the hash of the window matches the hash of p, compare the strings character by character to ensure it’s not a collision.
• Return the index if a match is found.

class Solution:
    def strStr(self, s: str, p: str) -> int:
        n, m = len(s), len(p)
        if m == 0: return 0
        if n < m: return -1
        base = 256
        mod = 101
        
        # Compute hash of p and first window of s
        hash_p = 0
        hash_s = 0
        power = 1
        for i in range(m):
            hash_p = (hash_p * base + ord(p[i])) % mod
            hash_s = (hash_s * base + ord(s[i])) % mod
            if i < m - 1:
                power = (power * base) % mod
                
        for i in range(n - m + 1):
            if hash_p == hash_s:
                if s[i:i+m] == p:
                    return i
            if i < n - m:
                hash_s = (hash_s - ord(s[i]) * power) % mod
                hash_s = (hash_s * base + ord(s[i+m])) % mod
                if hash_s < 0:
                    hash_s += mod
        return -1

Complexity

• Time: O(n + m) on average, O(nm) worst case due to collisions.
• Space: O(1)
• Notes: Efficient for finding multiple patterns or in streaming scenarios.