Implement strstr()

题目描述

解题方法

O(nm)

Have you considered these scenarios?

• needle or haystack is empty. If needle is empty, always return 0. If haystack is empty, then there will always be no match (return –1) unless needle is also empty which 0 is returned.
• needle’s length is greater than haystack’s length. Should always return –1.
• needle is located at the end of haystack. For example, “aaaba” and “ba”. Catch possible off-by-one errors.
• needle occur multiple times in haystack. For example, “mississippi” and “issi”. It should return index 2 as the first match of “issi”.
• Imagine two very long strings of equal lengths = n, haystack = “aaa…aa” and needle = “aaa…ab”. You should not do more than n character comparisons, or else your code will get Time Limit Exceeded in OJ.

Solution

class Solution(object):
    def strStr(self, haystack, needle):
        """
        :type haystack: str
        :type needle: str
        :rtype: int
        """
        if not haystack and not needle:
            return 0
        length_h = len(haystack)
        length_n = len(needle)

        if length_h < length_n:
            return -1

        for i in range(length_h - length_n + 1): # i的范围要注意
            j = 0
            while j <length_n: #从第一个char开始match
                if haystack[i+j] != needle[j]:
                    break
                j += 1
            if j == length_n: # match the whole string
                return i

        return -1

Reference