用 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

Arnab Chakraborty

更新於：2020-04-28

2K+ 瀏覽

搶得你的職業先機

完成課程以獲得認證

開始學習