Problem Statement:
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.
Examples:
Example 1:
Input:haystack = “sadbutsad”, needle = “sad”
Output:0
Explanation:
“sad” occurs at index 0 and 6.The first occurrence is at index 0, so we return 0.
Example 2:
Input:haystack = “leetcode”, needle = “leeto”
Output:-1
Explanation:
“leeto” did not occur in “leetcode”, so we return -1.
Constraints:
1 <= haystack.length, needle.length <= 104haystackandneedleconsist of only lowercase English characters.
Approach
- Loop through each index
iinhaystackwhere needle could start(0 to n - m). - For each
i, compare needle with the substring starting ati. - If all characters match,
return i. - If no match is found,
return -1.
Time Complexity:
Time Complexity = O(n * m)
Space Complexity:
Space Complexity = O(1)
Dry Run
Input: haystack = "hello", needle = "ll"
n = 5, m = 2 i = 0 j = 0 → haystack[0 + 0] = 'h' ≠ needle[0] = 'l' → break i = 1 j = 0 → haystack[1 + 0] = 'e' ≠ needle[0] = 'l' → break i = 2 j = 0 → haystack[2 + 0] = 'l' == needle[0] = 'l' j = 1 → haystack[2 + 1] = 'l' == needle[1] = 'l' → j == m → return 2
Output: Result: 2
Visualisation:
var strStr = function(haystack, needle) {
let n = haystack.length;
let m = needle.length;
for (let i = 0; i <= n - m; i++) {
let j = 0;
for (j = 0; j < m; j++) {
if (haystack[i + j] !== needle[j]) {
break;
}
}
if (j === m) {
return i;
}
}
return -1;
};
def strStr(haystack, needle):
n = len(haystack)
m = len(needle)
for i in range(n - m + 1):
j = 0
for j in range(m):
if haystack[i + j] != needle[j]:
break
else:
return i
return -1
int strStr(String haystack, String needle) {
int n = haystack.length();
int m = needle.length();
for(int i = 0; i <= n - m; i++) {
int j = 0;
for(j = 0; j < m; j++) {
if(haystack.charAt(i + j) != needle.charAt(j)) {
break;
}
}
if(j == m) {
return i;
}
}
return -1;
}
int strStr(string haystack, string needle) {
int n = haystack.length();
int m = needle.length();
for(int i = 0; i <= n - m; i++) {
int j = 0;
for(j = 0; j < m; j++) {
if(haystack[i + j] != needle[j]) {
break;
}
}
if(j == m) {
return i;
}
}
return -1;
}
int strStr(char* haystack, char* needle) {
int n = strlen(haystack);
int m = strlen(needle);
for(int i = 0; i <= n - m; i++) {
int j = 0;
for(j = 0; j < m; j++) {
if(haystack[i + j] != needle[j]) {
break;
}
}
if(j == m) {
return i;
}
}
return -1;
}
int StrStr(string haystack, string needle) {
int n = haystack.Length;
int m = needle.Length;
for(int i = 0; i <= n - m; i++) {
int j = 0;
for(j = 0; j < m; j++) {
if(haystack[i + j] != needle[j]) {
break;
}
}
if(j == m) {
return i;
}
}
return -1;
}
