切換
舊版
前往
大廳
主題

LeetCode - 28. Implement strStr() 解題心得

Not In My Back Yard | 2020-08-01 00:03:41 | 巴幣 0 | 人氣 161

題目連結:


題目意譯:
實作 strStr()。

回傳字串 needle 第一次在字串 haystack 中出現的索引值。如果 needle 不是 haystack 的一部分則回傳 -1 。



說明:
當 needle 是空字串時,要回傳什麼?這是一個適合在面試中提問的問題。
對於這題來說,當 needle 是空字串時會回傳 0 。此作法跟 C 語言的 strstr() 以及 Java 的 indexOf() 函式是一致的。

約束:
字串 haystack 和 needle 只由小寫英文字母組成。



範例測資:
範例 1:
輸入: haystack = "hello", needle = "ll"
輸出: 2

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


解題思維:
先判斷字串 needle 的長度,如果是 0 則直接回傳 0;如果大於字串 haystack 的長度,則直接回傳 -1。

剩下的情況就是直接跑過一次 haystack 字串。每遇到一個字元,判斷其與後面的字元組成的字串(要跟 needle 同長度)是不是一樣的字串。如果不是就繼續找下一個字元。如果是就回傳該位置的索引值。




此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。

創作回應

更多創作