Coder's Cat

LeetCode: Implement strStr()

2020-01-31

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!