How do you solve Find the Index of the First Occurrence in a String on LeetCode?

Find the Index of the First Occurrence in a String (LeetCode #28) can be solved using Brute Force or Optimal Solution (KMP Algorithm). The optimal approach is Optimal Solution (KMP Algorithm) with O(n + m) time complexity and O(m) space complexity. Key insight: Understanding the KMP algorithm can significantly reduce the time complexity of string matching problems.

What is the brute force solution for Find the Index of the First Occurrence in a String?

The brute force approach for Find the Index of the First Occurrence in a String is Brute Force, with O(n²) time complexity and O(1) space complexity. The brute force approach involves checking every possible starting position in the haystack for the needle. For each position, we compare the substring of the haystack with the needle until we find a match or exhaust all possibilities. The optimal Optimal Solution (KMP Algorithm) approach improves this to O(n + m).

What algorithm or data structure is used to solve Find the Index of the First Occurrence in a String?

Find the Index of the First Occurrence in a String uses the following concepts: Two Pointers, String, String Matching. The recommended patterns to study are: Hash Map, Array, Two Pointers.

What are the interview tips for Find the Index of the First Occurrence in a String?

When you first see this problem, clarify the constraints and edge cases, such as what to return if the needle is empty. Communicate your thought process clearly, explaining why you might start with a brute force approach before discussing optimizations. Mention edge cases like empty strings and cases where the needle is longer than the haystack.

What are common mistakes when solving Find the Index of the First Occurrence in a String?

Students often forget to handle the edge case where the needle is an empty string. Not considering the efficiency of their solution can lead to timeouts in larger inputs.

#28

Find the Index of the First Occurrence in a String

Easy

Two PointersStringString MatchingHash MapArrayTwo Pointers

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution (KMP Algorithm)★
Time	O(n²)	O(n + m)
Space	O(1)	O(m)

💡

Intuition

Time O(n + m)Space O(m)

The Knuth-Morris-Pratt (KMP) algorithm improves the search by avoiding unnecessary comparisons. It preprocesses the needle to create a 'partial match' table, which helps skip over parts of the haystack that have already been matched.

⚙️

Algorithm

3 steps

1Step 1: Create a partial match table for the needle, which indicates the longest prefix that is also a suffix.
2Step 2: Loop through the haystack and needle using two pointers. If characters match, move both pointers forward.
3Step 3: If characters do not match, use the partial match table to skip unnecessary comparisons in the needle.

solution.py28 lines

1# Full working Python code with comments
2
3def build_partial_match_table(needle: str) -> list:
4    table = [0] * len(needle)
5    j = 0
6    for i in range(1, len(needle)):
7        while j > 0 and needle[i] != needle[j]:
8            j = table[j - 1]
9        if needle[i] == needle[j]:
10            j += 1
11            table[i] = j
12    return table
13
14
15def strStr(haystack: str, needle: str) -> int:
16    if not needle:
17        return 0
18    table = build_partial_match_table(needle)
19    j = 0
20    for i in range(len(haystack)):
21        while j > 0 and haystack[i] != needle[j]:
22            j = table[j - 1]
23        if haystack[i] == needle[j]:
24            j += 1
25        if j == len(needle):
26            return i - j + 1
27    return -1
28

ℹ

Complexity note: The time complexity is O(n + m) where n is the length of the haystack and m is the length of the needle. This is because we preprocess the needle in O(m) time and then scan through the haystack in O(n) time. The space complexity is O(m) due to the storage of the partial match table.

1Understanding the KMP algorithm can significantly reduce the time complexity of string matching problems.
2Recognizing that the problem can be broken down into substring comparisons allows for efficient solutions.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.