28_Implement strStr()

[Easy]

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

Example 3 (need to pay attention)

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

Example 4 (need to pay attention)

Input: haystack = "", needle = "ll"
Output: -1

Example 5 (need to pay attention)

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

Example 6 (need to pay attention)

Input: haystack = "a", needle = "abc"
Output: -1

Solution 1: Sliding Window 滑动窗口

Idea:

• This is a clean brute-force algorithm. We can traverse all the possible starting points of haystack(from 0to

haystack.length() - needle.length()) and see if the following characters in haystackmatch those of needle.

Special cases:

• Both haystack and needle can be empty. If haystack is empty, needle is not, should return -1. If needle is empty, haystack is not, should return 0. If both empty, should return 0.

Time complexity: $O((n-k)k)$, where k is the number of characters in needle.

Code 1:

class Solution(object):
    def strStr(self, haystack, needle):
        """
        :type haystack: str
        :type needle: str
        :rtype: int
        """
        for i in range(len(haystack) - len(needle)+1):
            if haystack[i:i+len(needle)] == needle:
                return i
        return -1

Code 2:

class Solution(object):
    def strStr(self, haystack, needle):
        """
        :type haystack: str
        :type needle: str
        :rtype: int
        """
        if len(needle) == 0:
            return 0
        if len(haystack) == 0:
            return -1
        for i in range(len(haystack) - len(needle) + 1):
            for j in range(len(needle)):
                if haystack[i + j] != needle[j]:
                    break
            else:                                # when no break is triggered in the previous for loop
                return i
        return -1