leecode-28-实现 strStr()

实现 strStr() 函数。

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

1
2
3
4
5
6
7
8
示例 1:

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

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

说明:

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

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

解法一：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#!/usr/bin/env python
# -*- coding: utf-8 -*-
# author：sarizzm time:2020/12/28 0028

class Solution:
    def strStr(self, haystack, needle) :
        length_haystack = len(haystack)
        length_needle = len(needle)
        j = 0
        k = str('')
        if length_needle == 0:
            return 0
        if length_needle > length_haystack:
            return -1
        if length_needle == length_haystack:
            if haystack == needle:
                return 0
            else:
                return -1
        for i in range(length_haystack):
            temp = i
            while temp <= length_haystack - 1 and haystack[temp] == needle[j]:
                temp += 1
                j += 1
                if j >= length_needle:
                    return i
            j = 0
        return -1


print(Solution().strStr('hello', 'll'))
print(Solution().strStr('aaaaaa', 'baa'))
print(Solution().strStr('aaaaaa', ''))
print(Solution().strStr('', 'aad'))
print(Solution().strStr('jaassdfsfsgaaadsfdsfgaaasgsaa', 'aad'))
print(Solution().strStr('jaassdfsfsgaaadsfdsfgaaassgsaa', 'aaad'))
print(Solution().strStr('jaassdfsfsgaaadsfdsfgaaassgsaa', 'as'))

#执行用时：40 ms, 在所有 Python3 提交中击败了72.66%的用户
#内存消耗：14.9 MB, 在所有 Python3 提交中击败了11.96%的用户

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
class Solution {
  public int strStr(String haystack, String needle) {
    int L = needle.length(), n = haystack.length();
    if (L == 0) return 0;

    int pn = 0;
    while (pn < n - L + 1) {
      // find the position of the first needle character
      // in the haystack string
      while (pn < n - L + 1 && haystack.charAt(pn) != needle.charAt(0)) ++pn;

      // compute the max match string
      int currLen = 0, pL = 0;
      while (pL < L && pn < n && haystack.charAt(pn) == needle.charAt(pL)) {
        ++pn;
        ++pL;
        ++currLen;
      }

      // if the whole needle string is found,
      // return its start position
      if (currLen == L) return pn - L;

      // otherwise, backtrack
      pn = pn - currLen + 1;
    }
    return -1;
  }
}

//作者：LeetCode
//链接：https://leetcode-cn.com/problems/implement-strstr/solution/shi-xian-strstr-by-leetcode/
//来源：力扣（LeetCode）
//著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。