Description
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
|
C++ Solution
Time complexity: $O(MN)$ where M and N are the lengths of two string.
class Solution {
public:
int strStr(string haystack, string needle) {
int len1 = haystack.size();
int len2 = needle.size();
for(int i = 0; i <= len1 - len2; i++) {
int k = 0;
while(k < len2 && haystack[i+k] == needle[k])
k++;
if(k == len2) return i;
}
return -1;
}
};
|
Python Solution
Use str[i:length] to get the sub-string of str.
class Solution(object):
def strStr(self, haystack, needle):
"""
:type haystack: str
:type needle: str
:rtype: int
"""
if needle == '':
return 0
length = len(needle)
for i in range(len(haystack) - length+1):
if haystack[i:i+length] == needle:
return i
return -1
|
Preparing for an interview? Check out this!
