Description
https://leetcode.com/problems/implement-strstr/
Implement strStr().
Return the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack.
Example 1:
Input: haystack = "hello", needle = "ll" Output: 2
Example 2:
Input: haystack = "aaaaa", needle = "bba" Output: -1
Clarification:
What should we return when needle
is an empty string? This is a great question to ask during an interview.
For the purpose of this problem, we will return 0 when needle
is an empty string. This is consistent to C’s strstr() and Java’s indexOf().
Explanation
The problem is asking for the index of the first occurrence of needle in haystack.
The idea to solve the problem is that we check whether is able to loop through each character of needle from one position of haystack.
Time Complexity: O((m – n + 1) * n) = O(m * n). m is the length of haystack. n is the length of needle.
Java Solution
public class Solution {
public int strStr(String haystack, String needle) {
if (haystack == null || needle == null) {
return -1;
}
for (int i = 0; i < haystack.length() - needle.length() + 1; i++) {
int j;
for (j = 0; j < needle.length(); j++) {
if (haystack.charAt(i + j) != needle.charAt(j)) {
break;
}
}
if (j == needle.length()) {
return i;
}
}
return -1;
}
}
Python Solution
class Solution:
def strStr(self, haystack: str, needle: str) -> int:
if len(needle) > len(haystack):
return -1
for i in range(0, len(haystack) - len(needle) + 1):
j = 0
while j < len(needle):
if haystack[i + j] != needle[j]:
break
j += 1
if j == len(needle):
return i
return -1
i appreciate your work very nice explanation i have subscribed to youtube channel,it would be very helpful if we have test cases attached 🙂