Find the Index of the First Occurrence in a String

Slide the needle across the haystack, one start position at a time

time O(n * m)space O(1)

The brute-force approach is simpler than it sounds: try every possible starting position in the haystack, and at each one compare characters against the needle one at a time. The moment a mismatch happens, that start position is ruled out immediately — no need to keep comparing — and the search moves to the next start position.

Details

Animated on: haystack = "hello", needle = "ll" — find the index of the first occurrence of needle in haystack.

Problem:Find the Index of the First Occurrence in a StringEasy

Slide the needle across the haystack, one start position at a time

step 1 / 4

[0]

[1]

[2]

[3]

[4]

haystack="hello", needle="ll". Slide needle across haystack one position at a time, comparing character by character.

Pseudocode

1FUNCTION strStr(haystack, needle):
2  FOR i from 0 to length of haystack - length of needle:
3    matched = 0
4    WHILE haystack[i + matched] == needle[matched]:
5      add 1 to matched
6    IF matched == length of needle: RETURN i
7  RETURN -1

← / → step · space play · Home restart

Every step in words

Show all 4 steps

haystack="hello", needle="ll". Slide needle across haystack one position at a time, comparing character by character.
Position 0: h[0]='h' != n[0]='l' — no match, slide right.
Position 1: h[1]='e' != n[0]='l' — no match, slide right.
Position 2: all 2 characters of "ll" matched — found!

Now solve it yourself

Watching is the first half. The second is writing it without the animation.

Solve Find the Index of the First Occurrence in a String in the editor All Strings problems Back to roadmap