LeeCode每日一题-实现strStr()

Serepta ·

更新时间:2024-09-21

· 806 次阅读

【前言】坚持日更LeeCode刷题系列
不积跬步,无以至千里;不积小流,无以成江海。愿与诸君共勉！

【题目】28.实现strStr()函数
题目描述：实现 strStr() 函数。

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

示例:

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

说明:

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

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

思路一:通过python正则表达式中的search方法，匹配字符串。具体代码如下：

import re
class Solution(object):
    def strStr(self, haystack, needle):
        """
        :type haystack: str
        :type needle: str
        :rtype: int
        """
        result =  re.search(pattern = needle,string = haystack)
        if result == None:
            return -1
        else:
            return result.span()[0]

运行结果：
在这里插入图片描述
关于其中一些知识的链接：

Python 正则表达式

思路二:当然，我们能否不调用库函数来实现呢？显然是可以的，暴力遍历很容易想到，但是别忘了还有KMP算法，下面是我借用KMP算法思想，结合python列表中一些常用函数编写的代码，具体内容如下：

class Solution(object):
    def strStr(self, haystack, needle):
        """
        :type haystack: str
        :type needle: str
        :rtype: int
        """
        list1 = list(haystack)
        list2 = list(needle)
        if len(list2) == 0:
            return 0
        elif len(list1) == 0:
            return -1
        else:
            count = list1.count(needle[0])  #算出needle开头字母在haystack中的个数
            flag = 0  #用于补上被pop掉后index的改变值
            for i in range(count): #很显然我们只要遍历开头字母出现个数的次数
                index = list1.index(needle[0]) #通过index返回该字母所在位置的索引
                if len(list1[index:]) < len(list2): #当匹配字符串长度大于可比较字符串长度时，直接返回
                    return -1
                if list2 == list1[index:index+len(list2)]:
                    return index + flag  
                    break
                else:
                    list1.pop(index) #若匹配失败，则把此字母弹出
                    flag = flag+1
            return -1

运行结果：
在这里插入图片描述