Leetcode筆記-(簡單)28. 實作 strStr()

筆記

• 題目
• 示例
• 說明
• 代碼

題目

給定一個 haystack 字元串和一個 needle 字元串，在 haystack 字元串中找出 needle 字元串出現的第一個位置 (從0開始)。如果不存在，則傳回 -1。

示例

示例1

輸入: haystack = "hello", needle = "ll"
輸出: 2
           

示例2

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

說明

當 needle 是空字元串時，我們應當傳回什麼值呢？這是一個在面試中很好的問題。

對于本題而言，當 needle 是空字元串時我們應當傳回 0 。這與C語言的 strstr() 以及 Java的 indexOf() 定義相符。

代碼

python

思路：用needle元素依次跟haystack比較，對得上的元素個數等于needle的元素個數，說明找到了，就傳回第一個對應元素，否則傳回-1。（若needle元素個數為0，則直接傳回0）。

class Solution:
    def strStr(self, haystack: str, needle: str) -> int:
        num1 = len(haystack)
        num2 = len(needle)

        if num2 == 0:
            return 0

        count = 0
        if num1 != num2:
            temp = num1 - num2 + 1
        else:
            temp = 1

        for i in range(temp):
            for j in range(num2):
                if haystack[i + j] == needle[j]:
                    count += 1

            if count == num2:
                return i
            else:
                count = 0

        return -1 
           

執行結果：通過

執行用時：52 ms, 在所有 Python3 送出中擊敗了31.93% 的使用者

記憶體消耗：13.6 MB, 在所有 Python3 送出中擊敗了6.67% 的使用者