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

You're given two strings, haystack and needle. Locate the first position in haystack where needle appears as a contiguous substring and return that index; if needle never occurs in haystack, return -1.

Input Format
Implement strStr(haystack, needle). Inputs below show JavaScript function arguments; there is no stdin parsing.
Output Format
Return the result described in the statement.

Sample Input and Output

Example 1 · Run Sample

Input
haystack = "sadbutsad"
needle = "sad"
Output
0

Example 2

Input
haystack = "leetcode"
needle = "leeto"
Output
-1
Constraints
  • 1 <= haystack.length, needle.length <= 10^4
  • haystack and needle consist of lowercase English letters
Test Cases (2)
Case 1
Args: ["sadbutsad","sad"] Expected: 0
Case 2
Args: ["leetcode","leeto"] Expected: -1
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.

javascript
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