用 Python 实现 strStr()

假设我们有两个字符串 str 和 sub_str。我们必须找到 sub_str 在 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))

输入

haystack = "helloworld"
needle = "lo"

输出

3

更新于：2020-04-28

2K+ 浏览

抢得你的职业先机

完成课程以获得认证

开始学习
广告