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.

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