Find the Index of the First Occurrence in a String(#28)
Category: String, Two Pointer, Brute Force
🧩 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
Input: haystack = "leetcode", needle = "leeto"
Output: -1
Input: haystack = "abc", needle = ""
Output: 0
🧠 Approach
We solve this using a **Brute Force Substring Matching** approach:
• **Edge Case Check**: If `needle` is an empty string, return 0.
• **Loop Through Haystack**: Iterate from index 0 to `haystack.length - needle.length`.
• **Match Substring**: For each index, compare characters from `needle` with corresponding characters in `haystack`.
• **Return Index**: If all characters match, return the current index.
• **No Match**: If no match is found after the loop, return -1.
This approach runs in O(n*m) time where n is the length of `haystack` and m is the length of `needle`.
💻 Code
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)
Space: O(1)