[LeetCode]题解（python）：028-Implement strStr()

题目来源：

　　https://leetcode.com/problems/implement-strstr/

---

题意分析：

　　输入两个字符串haystack和needle，如果needle是haystack的一个子串，那么返回这个子串在haystack出现的第一个位置，否则返回-1.

---

题目思路：

　　这个题目是简单题，直接暴力解决就可以了。从i=0出发，如果遇到haystack[i] == needle[0]，那么判断从这个出发能不能构成needle，如果可以则返回i。直到i到最后一个字符的长度小于needle的长度。如果前面没有返回值，那么返回-1.时间复杂度是（O（(m - n) * n)).

---

代码（python）：

　　

 class Solution(object):

     def strStr(self, haystack, needle):

         """

         :type haystack: str

         :type needle: str

         :rtype: int

         """

         size1 = len(haystack)

         size2 = len(needle)

         if size2 == 0:

             return 0

         if size1 < size2:

             return -1

         i = 0

         while i < size1:

             if size1 - i < size2:

                 return -1

             if haystack[i] == needle[0]:

                 j = 1

                 while j < size2:

                     if haystack[i + j] != needle[j]:

                         break

                     j += 1

                 if j == size2:

                     return i

             i += 1

         return -1

---

转载请注明出处：http://www.cnblogs.com/chruny/p/4893126.html