LeetCode 28. Implement strStr()

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.

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

Example 1:

Input: haystack = "hello", needle = "ll"
Output: 2

Example 2:

Input: haystack = "aaaaa", needle = "bba"
Output: -1

Example 3:

Input: haystack = "", needle = ""
Output: 0

Constraints:

• 0 <= haystack.length, needle.length <= 5 * 104
• haystack and needle consist of only lower-case English characters.

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.

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

• Time Complexity:

• Time complexity: O(M – N), where M is the length of the haystack and N is the length of the needle. We compute a substring of length L in a loop, which is executed (M – N) times.
• Space complexity: O(1).