📘 題目敘述
給定兩個字串 haystack 與 needle，請找出 needle 在 haystack 中第一次出現的位置索引。
若 needle 不是 haystack 的子字串，則回傳 -1。
條件限制
1 ≤ haystack.length, needle.length ≤ 10^4haystack與needle只包含小寫英文字母
🧠 解題思路
我的做法是最直觀的「暴力比對」方式：
- 把
haystack中的每一個位置，都當作可能的起點 - 從這個起點開始，嘗試完整比對
needle - 只要有任何一個字元不相同，就代表這個起點不可能成功
- 若某個起點能把
needle全部比對完成，這個起點就是答案
因為題目只要求「第一次出現的位置」，所以一旦找到，就可以立刻回傳，不需要再繼續搜尋。
所有變數
pos：目前在haystack中嘗試比對的起始位置n：haystack的長度m：needle的長度check：用來判斷「目前這個起點是否能完整匹配needle」
🪜 主要流程步驟
前置判斷：長度不可能的情況
- 如果
haystack的長度小於needle - 那不可能出現完整匹配
- 直接回傳
-1
外層邏輯：枚舉所有可能的起點
我用 pos 從 0 開始，一路往右移動：
- 每一個
pos都代表「假設needle從這裡開始出現」 - 只要還沒超出
haystack，就繼續嘗試
內層邏輯：從目前起點開始比對 needle
對於固定的 pos：
- 我從
needle的第0個字元開始比 - 依序檢查：
haystack[pos + i]是否等於needle[i]
在比對過程中會遇到幾種情況：
情況一：索引超出範圍
- 若
pos + i >= n - 代表剩下的
haystack長度不夠 - 這個起點直接失敗
情況二：字元不相等
- 只要有任一個字元不同
- 就代表這個起點不可能成功
- 立刻停止比對，換下一個
pos
情況三：完整比對成功
- 如果
needle的所有字元都成功比對 - 代表在
pos這個位置找到答案 - 直接回傳
pos
全部嘗試完仍找不到
- 若所有可能的起點都試過
- 仍然沒有任何一個成功
- 回傳
-1
為什麼這樣想是合理的？
- 題目規模不大，允許
O(n * m)的暴力解 - 每一個起點的比對邏輯都很清楚
- 沒有額外資料結構，直覺且好驗證
- 非常適合當作字串比對題的「基礎模板」
💻 程式碼實作
class Solution {
public:
int strStr(string haystack, string needle) {
int pos = 0;
int n = haystack.size();
int m = needle.size();
if (n < m) {
return -1;
}
while (pos < n) {
bool check = true;
for (int i = 0; i < m; i++) {
if (pos + i >= n) {
check = false;
break;
}
if (haystack[pos + i] != needle[i]) {
check = false;
break;
}
}
if (check) {
return pos;
}
pos++;
}
return -1;
}
};
🔗 題目連結
https://leetcode.com/problems/find-the-index-of-the-first-occurrence-in-a-string/