在 Python 中实现 strStr()

pythonserver side programmingprogramming更新于 2025/10/31 17:48:17

假设我们有两个字符串 str 和 sub_str。我们必须在 str 中找到 sub_str 的第一次出现。因此，如果字符串 str 是"helloworld"，而子字符串是"lo"，则结果将为 3。

这可以使用 C 中的 strstr() 函数来完成。我们必须设计另一个类似于 C 中的 strstr() 的函数。

要解决这个问题，请按照以下步骤 −

i := 0, j := 0, m := sub_str 的长度和 n := str 的长度
如果 m = 0，则返回 0
当 i < n 和 n – i + 1 = m，执行
- 如果 str[i] = sub_str[j]，则
  - temp := j
  - 当 j < m 和 i < n 且 sub_str[j] == str[j] 时，执行
    - 将 i 和 j 增加 1
  - 如果 j = m，则返回 temp
  - i := temp + 1
  - j := 0
- 否则将 i 增加 1
返回 -1

让我们看一下实现以便更好地理解

示例 (Python)

class Solution(object):
   def strStr(self, haystack, needle):
      """
      :type haystack: str
      :type needle: str
      :rtype: int
      """
      i = 0
      j = 0
      m = len(needle)
      n = len(haystack)
      if m ==0:
         return 0
      while i<n and n-i+1>=m:
         if haystack[i] == needle[j]:
            temp = i
            while j<m and i<n and needle[j]==haystack[i]:
               i+=1
               j+=1
            if j == m:
               return temp
            i= temp+1
            j = 0
         else:
            i+=1
      return -1
haystack = "helloworld"
needle = "lo"
ob1 = Solution()
print(ob1.strStr(haystack, needle))