Q28 Implement strStr()

Implement strStr().

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

Example 1:
Input: haystack = "hello", needle = "ll"
Output: 2
Example 2:
Input: haystack = "aaaaa", needle = "bba"
Output: -1
解题思路:

此题即实现Python中内置函数 find() 的功能。简单方法就是逐个字符比较,当匹配失效后,将子串重新移到开始位置,主串回退前面已经匹配的n个字符,然后继续比较。时间复杂度 O(m*n)

注意点:

此题可采用 KMP 算法求解,时间复杂度可以降为 O(m+n),后续补充。

Python实现:
class Solution:
    def strStr(self, haystack, needle):
        """
        :type haystack: str
        :type needle: str
        :rtype: int
        """
        haylen = len(haystack)
        needlen = len(needle)
        if needlen == 0:
            return 0
        if haylen < needlen:
            return -1
        i = 0; j = 0; count = 0;
        while i < haylen:
            if j < needlen and haystack[i] == needle[j]:
                j += 1
                count += 1
            elif count > 0 and haystack[i] != needle[j]:  # needle从头开始比较
                j = 0  
                i -= count  # 回退count个字符
                count = 0
            i += 1  
            if count == needlen:
                return i - count
        return -1

a = "ississip"
b = "issip"
c = Solution()
print(c.strStr(a,b))  # 3

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • Leetcode【423、593】

    这道题是给一个字符串,其中包含字母顺序打乱的英文单词表示的数字 0 - 9。按升序输出原始的数字。

    echobingo
  • Q121 Best Time to Buy and Sell Stock

    Say you have an array for which the ith element is the price of a given stock on...

    echobingo
  • Leetcode【470、478、497、519、528】

    这道题是用等概率的 Rand7()([1, 7])产生等概率的 Rand10()([1, 10])。

    echobingo
  • 28. 实现strStr()

    给定一个 haystack 字符串和一个 needle 字符串,在 haystack 字符串中找出 needle 字符串出现的第一个位置 (从0开始)。如果不存...

    祝你万事顺利
  • 分享用于学习C++音频处理的代码示例

    与《分享用于学习C++图像处理的代码示例》为姊妹篇。 为了便于学习C++音频处理并研究音频算法, 俺写了一个适合初学者学习的小小框架。 麻雀虽小五脏俱全,仅仅考...

    cpuimage
  • JavaBean是什么

    Java Bean 实际是就是一个普通的 Java Class,但是需要满足三个要求 1、所有属性为 private,只允许通过getter方法和setter...

    赵哥窟
  • Android Volley 源码解析(三),图片加载的实现

    在上一篇文章中,我们一起深入探究了 Volley 的缓存机制,通过源码分析对缓存的工作原理进行了了解,这篇文章将带大家一起探究「Volley 图片加载的实现」,...

    developerHaoz
  • CentOS 7 上部署Mono 4 和Jexus 5.6

    概述 在这篇文章中我们将讨论如何在CentOS 7操作系统,安装 jexus、 mono 和 配置 jexus,因此它将能够在这种环境中运行一个asp.net ...

    张善友
  • Windows Community Toolkit 3.0 - CameraPreview

    Windows Community Toolkit 3.0 于 2018 年 6 月 2 日 Release,同时正式更名为 Windows Community...

    Shao Meng
  • 新闻动态|“中国式过马路”怎么破?北京交管正式采用“腾讯优图人脸识别技术”

    近日,北京市公安交通管理局与腾讯优图实验室正式开展合作,在处理非机动车驾驶员和行人违法行为时,试点采用优图人脸识别技术实现对违法人员信息的快速核实。

    优图实验室

扫码关注云+社区

领取腾讯云代金券