【求知=>算法】实现 strStr()

发布时间:2022-01-15编辑:RainNight阅读(383)

    实现 strStr()


    实现 strStr()函数。

    给你两个字符串haystackneedle ,请你在 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)
      

关键字求知=>算法

Collect from 雨夜的博客 雨夜的博客