EasyTwo PointersString

Implement strStr()

1 approach, code in every language

Given two strings, a haystack and a needle, return the index of the first position in the haystack where the needle appears as a contiguous substring, or -1 if the needle never occurs.

By convention, an empty needle is considered to match at index 0.

Example 1

Input: haystack = "hello", needle = "ll"

Output: 2

The substring "ll" begins at index 2 of "hello".

Example 2

Input: haystack = "aaaaa", needle = "bba"

Output: -1

There is no place in "aaaaa" that lines up with "bba", so the search fails.

Constraints

1 ≤ haystack.length, needle.length ≤ 10^4
haystack and needle consist of lowercase English letters.

Sliding Window Compare

Try each possible starting offset in the haystack and compare the needle character by character until either a full match is found or the offset runs past the last feasible position.

Loading animation…

Intuition

The most direct way to find a substring is to line the needle up under the haystack at position 0, check whether every character agrees, and if not, slide it one step to the right and try again. We only need to test offsets where the needle can still fit, which is up to length(haystack) - length(needle). For faster matching, the Knuth-Morris-Pratt (KMP) algorithm precomputes a prefix table so that after a partial match it can skip ahead without rechecking characters, giving linear time in the worst case; the straightforward scan below is simpler and fast enough for these limits.

Algorithm walkthrough

1If the needle is empty, return 0 right away by convention.
2Loop the starting offset from 0 up to length(haystack) minus length(needle).
3At each offset, compare the needle against the haystack one character at a time.
4If all characters of the needle match, return the current offset as the answer.
5If the loop finishes with no full match, return -1.

Implementation

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

Time

O(n * m)

Space

O(1)

The plain scan can compare up to m characters at each of n offsets; KMP improves this to O(n + m).

Create a free account to see the solution

You get the step-by-step animation, the intuition and clean code in every language. Free, no credit card.

Create a free account Already have an account? Sign in

Back to Strings

After the pattern

Now solve one you haven't seen.

Reading a pattern isn't the same as using it. The practice set has 1,194 original problems on the same techniques, each graded in your browser.

Open the practice set Start the FDE path

1,194 problems · 15,062 graded tests · free