Find the Index of the First Occurrence in a String Easy 0 attempts
LeetCode ↗

Find the Index of the First Occurrence in a String

Easy StringHash Table LeetCode

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

Sample Input
haystack = "sadbutsad", needle = "sad"
Sample Output
0
Constraints
  • 1 <= haystack.length, needle.length <= 10^4
  • haystack and needle consist of lowercase English letters
Test Cases
Case 1
Args: ["sadbutsad","sad"] Expected: 0
Topics
StringHash Table

Scan through the haystack checking for a substring match at each position. For a simple approach, use the built-in indexOf. For larger inputs, KMP or Rabin-Karp provide better worst-case performance.

function strStr(haystack, needle) {
  if (needle === '') return 0;
  return haystack.indexOf(needle);
}

Time: O(n × m) for naive approach; O(n + m) with KMP Space: O(1) for naive; O(m) for KMP

Saved in this browser only. Private to you.

JavaScript