Find the Index of the First Occurrence in a String
(#28), Easy
Category: String, Two Pointer
Problem Statement
Implement strStr(). 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. If needle is an empty string, return 0.
Examples
Input: haystack = "sadbutsad", needle = "sad"
Output: 0
Explanation: 'sad' starts at index 0.
Input: haystack = "leetcode", needle = "leeto"
Output: -1
Explanation: 'leeto' is not present in 'leetcode'.
Input: haystack = "abc", needle = ""
Output: 0
Explanation: If needle is empty, return 0.
Approach
Brute Force Substring Matching
- Check if the `needle` is an empty string. If yes, return 0.
- If `haystack.length < needle.length`, return -1 immediately.
- Loop from index `i = 0` to `haystack.length - needle.length`.
- At each index `i`, loop through the characters of `needle` and compare with `haystack[i + j]`.
- If all characters match, return the index `i`.
- If no match is found after the loop, return -1.
var strStr = function(haystack, needle) {
if (needle.length === 0) {
return 0;
}
if (haystack.length < needle.length) {
return -1;
}
for (let i = 0; i <= haystack.length - needle.length; i++) {
let match = true;
for (let j = 0; j < needle.length; j++) {
if (haystack[i + j] !== needle[j]) {
match = false;
break;
}
}
if (match) {
return i;
}
}
return -1;
};Complexity
Time: O(n * m), where n = haystack.length and m = needle.length
Space: O(1)