LeetCode Problem 28-Implement strStr()

Posted on | In | Visitors

实现 strStr() 函数。

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

示例 1:

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

示例 2:

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

说明:

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

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

思路一

判断两个字符串的长度，然后在循环中进行比较（循环次数是两个字符串长度的差值）。时间复杂度 $O(mn)$，$m,n$ 分别是两个字符串的长度。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:
    def strStr(self, haystack: str, needle: str) -> int:
        m, n = len(haystack), len(needle)
        if m < n:
            return -1
        if n == 0:
            return 0
        for i in range(m - n + 1):   # 注意+1，两个串长度相同的情况
            j = 0
            while j < n:
                if haystack[i + j] != needle[j]:
                    break
                else:
                    j += 1
            if j == n:
                return i
        return -1

相似问题

  1. Shortest Palindrome
  2. Repeated Substring Pattern
此时不赞何时赞！