创建于20170313
原文链接：https://leetcode.com/problems/implement-strstr/

题目

Implement strStr().

Returns the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack.

题解

class Solution(object):
    def strStr(self, haystack, needle):
        """
        :type haystack: str
        :type needle: str
        :rtype: int
        """
        m=len(haystack)
        n=len(needle)
        if m < n:
            return -1
        elif m==0 or n==0:
            return 0
            
        for i in range(m-n+1):
            j=0
            while(j<n):
                if haystack[i+j] != needle[j]:
                    break
                else:
                    j+=1
            if j==n:
                return i
        return -1

解析

时间复杂度: O(N^2)

扩展