admin 管理员组

文章数量: 887021

字符串

Leetcode 28题

1、题目描述

# Given two strings needle and haystack, return the index of the first 
# occurrence of needle in haystack, or -1 if needle is not part of haystack. 
# 
#  
#  Example 1: 
# 
#  
# Input: haystack = "sadbutsad", needle = "sad"
# Output: 0
# Explanation: "sad" occurs at index 0 and 6.
# The first occurrence is at index 0, so we return 0.
#  
# 
#  Example 2: 
# 
#  
# Input: haystack = "leetcode", needle = "leeto"
# Output: -1
# Explanation: "leeto" did not occur in "leetcode", so we return -1.
#  
# 
#  
#  Constraints: 
# 
#  
#  1 <= haystack.length, needle.length <= 10⁴ 
#  haystack and needle consist of only lowercase English characters.

2、代码实现

class Solution:def next(self, needle):next_arr = [0] * (len(needle) + 1)i = 0j = 1next_arr[0] = -1while j < len(needle):if i == -1 or needle[i] == needle[j]:i += 1j += 1next_arr[j] = ielse:i = next_arr[i]return next_arrdef strStr(self, haystack: str, needle: str) -> int:next_arr = self.next(needle)i = 0j = 0ix = -1while i < len(needle) and j < len(haystack):if i == -1 or needle[i] == haystack[j]:i += 1j += 1else:while i != -1 and needle[i] != haystack[j]:i = next_arr[i]if i == len(needle):ix = j-len(needle)return ix# leetcode submit region end(Prohibit modification and deletion)if __name__ == '__main__':so = Solution()needle = "abcabcmn"haystack = "abcababcabcmncabcmn"res = so.strStr(haystack, needle)print(res)

3、解题思路

  • next数组的构建和匹配的过程都采用双指针的策略。
  • 构建next数组，next数组的含义是指记录首位固定的情况下，当前字符之前的最长公共子串的长度。
  • next数组用一个while循环就可以实现，如果存在回溯的情况j指针不会移动。
  • 在匹配的过程中，如果不匹配要进行回溯。

4、next数组

  • 假设模式串是abcabeeeabcabcmncabcmn，abcabe和abcabc匹配时，e和c不匹配。
  • 但是abcabe和abcabc存在公共相同的子串abcab，abcab也存在公共子串ab。
  • abcabe和abcabc中的ab子串都相同，所以直接使用abcabeeeabcabcmncabcmn匹配。

本文标签： 字符串

版权声明：本文标题：字符串 内容由网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：http://www.freenas.com.cn/jishu/1686943459h49566.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。