实现 strStr()

实现 strStr()

实现 strStr()函数。

给你两个字符串haystack 和 needle ，请你在 haystack 字符串中找出 needle 字符串出现的第一个位置（下标从 0 开始）。如果不存在，则返回-1 。

说明：

当 needle 是空字符串时，我们应当返回什么值呢？这是一个在面试中很好的问题。

对于本题而言，当 needle 是空字符串时我们应当返回 0 。这与 C 语言的strstr()以及 Java 的 indexOf() 定义相符。

示例 1：

输入：haystack = “hello”, needle = “ll”

输出：2

示例 2：

输入：haystack = “aaaaa”, needle = “bba”

输出：-1

示例 3：

输入：haystack = “”, needle = “”

输出：0

提示： 

0 <= haystack.length, needle.length <= 5 * 104 

haystack 和 needle 仅由小写英文字符组成

解题思路

什么是kpm算法？ > KMP算法是一种改进的字符串匹配算法，由D.E.Knuth，J.H.Morris和V.R.Pratt提出的，因此人们称它为克努特—莫里斯—普拉特操作（简称KMP算法）。KMP算法的核心是利用匹配失败后的信息，尽量减少模式串与主串的匹配次数以达到快速匹配的目的。KMP算法的 [时间复杂度]O(m+n) 。

• 1. Kpm算法方式
  • 定义字符串haystack，并赋值为haystack = “hello”;
  • 定义字符串needle，并赋值为needle = “ll”;
  • 定义i和j,并赋值为i = 0 j = 0;
  • 判断字符串为空，返回0，长度为0，返回空；
  • 判断haystack的长度大于i和needle的长度大于j;
  • 如果当前haystack的值等于needle的值，就在原来的基础上加一i+=1 j+=1;
  • 否则j = 0,i如果不匹配，就回退，从第一次匹配的下一个开始；
  • 如果就等于needle的长度，就返回I减去jreturn I - j;

  • 最后返回-1；

    haystack = "hello"
    needle = "ll"
    
    # haystack = "aaaaa"
    # needle = "bba"
    #
    # haystack = ""
    # needle = ""
    
    i = 0
    j = 0
    
    if len(haystack)==0:
    return 0
    if len(needle)==0:
    return 0
    
    while i< len(haystack) and j < len(needle):
    if haystack[i] == needle[j]:
        i+=1
        j+=1
    else:
        # 如果不匹配，就回退，从第一次匹配的下一个开始，
        i = i -j + 1
        j = 0
    
    if j ==  len(needle):
        return i - j
    return -1
    

  1. 双指针方式
  • 定义字符串haystack，并赋值为haystack = “hello”;
  • 定义字符串needle，并赋值为needle = “ll”;
  • 获取haystack的长度，并赋值为n = len(haystack);
  • 定义left和right,并赋值为left = 0 right = len(needle);

  • 如果right等于1，返回0；

  • 判断n大于等于right;
  • 如果haystack左右值为下标等于needlehaystack[left: right] == needle,返回left;
  • 就在原来的基础上加一left+=1 right+=1;

  • 最后返回-1；

    haystack = "hello"
    needle = "ll"
    n = len(haystack)
    left = 0
    right = len(needle)
    if right == 0:
    return 0
    while right <= n:
    if haystack[left: right] == needle:
        return left
    left += 1
    right += 1
    return -1
    

  1. 通过find方式
  2. 定义字符串haystack，并赋值为haystack = “hello”;

  3. 返回查询找到的needle；

     haystack = "hello"
     needle = "ll"
     return haystack.find(needle)