leetcode28.实现strStr()

发布于 2021-04-17 05:30 ，所属分类：知识学习综合资讯


题目描述

题目描述

实现 strStr() 函数。


给定一个 haystack 字符串和一个 needle 字符串，在 haystack 字符串中找出 needle 字符串出现的第一个位置 (从0开始)。如果不存在，则返回 -1。




示例

输入: haystack = "hello", needle = "ll"输出: 2
输入: haystack = "aaaaa", needle = "bba"输出: -1

（左右滑动查看完整内容）




说明

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

  • 对于本题而言，当 needle 是空字符串时应当返回 0 。


  • 难度：简单

  • 标签：双指针、字符串





分析和题解

方法一

双指针法：从两字符串的第一个元素开始比较，如果相同，两指针都自增1，指向下一个元素；如果不相同，指针n归零，从头开始，指针h指向下一个元素，直到遍历完整个字符串。最后如果n等于needle的长度，则说明存在，返回h-len(needle)，否则不存在，返回-1。


class Solution:    def strStr(self, haystack: str, needle: str) -> int:        if needle == '': return 0        h, n = 0, 0  # 双指针        while h<len(haystack) and n<len(needle):  # 从两字符串的第一个元素开始比较            if haystack[h] == needle[n]:  # 如果相同，两指针都自增1，指向下一个元素                h += 1                n += 1            else:  # 不相同，则指针n归零，从头开始，指针h指向下一个元素                h = h-n+1                n = 0        if n == len(needle):            return h-len(needle)        else:return -1

（左右滑动查看完整代码）




方法二

利用切片形成一个滑动窗口，沿着字符串逐步移动滑动窗口，将窗口内的子串与 needle 字符串比较。


class Solution:  def strStr(self, haystack: str, needle: str) -> int:    for i in range(len(haystack)-len(needle)+1):      if haystack[i:i+len(needle)] == needle:        return i    return -1

（左右滑动查看完整代码）




方法三

使用python的内置函数find()


class Solution:  def strStr(self, haystack: str, needle: str) -> int:    return haystack.find(needle)

（左右滑动查看完整代码）




相关资源