🎨Now live: Try our Free AI Image Generation Feature

Intuition
The problem requires finding the first occurrence of the substring needle
within the string haystack
. If needle
is not found in haystack
, we return -1.
Approach
- Edge Case Handling:
Check if
needle
is empty. If it is, return 0 immediately because an emptyneedle
is always found at the beginning ofhaystack
. - Iterate Through
haystack
: Use a loop to iterate throughhaystack
. For each positioni
inhaystack
, check if the substring starting ati
and of length equal to the length ofneedle
matchesneedle
. - Return the Index:
If a match is found, return the index
i
whereneedle
starts inhaystack
. - Return -1 if Not Found:
If the loop completes without finding
needle
, return -1.
Complexity
Time Complexity:
O((n-m+1) * m) where n
is the length of haystack
and m
is the length of needle
. The worst-case scenario involves checking all possible substrings of length m
in haystack
.
Space Complexity:
O(1) extra space, apart from input space.
Code
C++
class Solution {
public:
int strStr(string haystack, string needle) {
if (haystack.length() < needle.length()) {
return -1;}
for (int i = 0; i <= haystack.length() - needle.length(); i++) {
if (haystack.substr(i, needle.length()) == needle) {
return i;
}}
return -1;
}};
Python
class Solution:
def strStr(self, haystack: str, needle: str) -> int:
if len(haystack) < len(needle):
return -1
for i in range(len(haystack) - len(needle) + 1):
if haystack[i:i + len(needle)] == needle:
return i
return -1
Java
class Solution {
public int strStr(String haystack, String needle) {
if (haystack.length() < needle.length()) {
return -1;
}
for (int i = 0; i <= haystack.length() - needle.length(); i++) {
if (haystack.substring(i, i + needle.length()).equals(needle)) {
return i;
}
}
return -1;
}
}
JavaScript
var strStr = function (haystack, needle) {
if (haystack.length < needle.length) {
return -1;
}
for (let i = 0; i <= haystack.length - needle.length; i++) {
if (haystack.substring(i, i + needle.length) === needle) {
return i;
}
}
return -1;
};