題目連結:
題目意譯:
實作 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 同長度)是不是一樣的字串。如果不是就繼續找下一個字元。如果是就回傳該位置的索引值。
此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。