Re: [閒聊] 每日LeetCode

[umi0912umi (大空スバル的香腸)]

28. Find the Index of the First Occurrence in a String

題目 :

給2個字串needle和haystack，
回傳needle第一次出現在haystack中的index，
如果needle不在haystack中則回傳-1


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.


思路 :

for迴圈跑haystack
找到第一個字母符合的就比對一下


=================================

python code :

class Solution:
    def strStr(self, haystack: str, needle: str) -> int:
        len_needle = len(needle)
        for i in range(len(haystack)) :
            if haystack[i] == needle[0] :
                if i+len_needle-1 < len(haystack) :
                    if haystack[i:i+len_needle] == needle :
                        return i
        return -1

python直接可以[i:i+長度]比對起來比較方便
其他語言應該不太能這樣寫??
但我看這題related topic有two pointer
不過不太懂要怎麼用two pointer
有大師要解惑嗎??




--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 223.136.203.175 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1677822655.A.041.html
推 idiont: Rabin-Karp algorithm嗎 我是懶得自己寫字串比對 直接stri
→ idiont: ng.find()
→ idiont: 看一下討論區說的two-pointer都是O(nm)的做法 沒有O(n+m)
推 NTHUlagka: 這題要O(m+n)就KMP吧 O(m*n)蠻接近不會過的邊緣了
→ umi0912umi: 沒聽過KMP 研究一下那是啥 我好爛QQ
→ idiont: kmp z-value 還有上面那個 都是線性的字串比對演算法