28 Implement strStr()

1. Description

Implement strStr().

 

Given two strings needle and haystack, return the index of the first occurence of needle in haystack, or -1 if needle is not part of haystack.

 

What sould 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().

 

constraints :

• 1 <= haystack.length, needle.length <= 104
• haystack and needle consist of only lowercase English characters.

2. Algorithms

There are method index() in Python, but we will use control statement to solve this problem.

1. If the needle is an empty string return 0
2. Initialize index of haystack as 'i'
3. Until i is bigger than lenth of haystack, check if there are needle in haystack. (haystack[i:i+len(needle)] == needle)
   1. Return its index under condition.
   2. Incrementy i by 1.
4. If needle is not part of haystack(code out of loop), return -1.

The time complexity of algorithms will be O(N).

3. Codes

class Solution:
    def strStr(self, haystack: str, needle: str) -> int:
        if len(needle) == 0 : return 0 
        i = 0 
        
        while i < len(haystack) : 
            if haystack[i:i+len(needle)] == needle : 
                return i 
            i += 1
        return -1

4. Conclusion