📘 題目敘述
給定一個長度為 n 的字串 s，內容只包含小寫英文字母。
請回傳最小的索引 i，使得：
s[i] == s[n - i - 1]
如果不存在這樣的索引，回傳 -1。
條件限制
1 <= n == s.length <= 100s只包含小寫英文字母
🧠 解題思路
我這題的想法很直接，就是從字串兩端往中間檢查。
因為題目要找的是最小的 i，滿足：
- 左邊是
s[i] - 右邊對應位置是
s[n - i - 1]
所以我只要從小到大枚舉 i，每次檢查這兩個位置的字元有沒有一樣。 只要第一次出現一樣，我就可以立刻回傳，因為那一定就是最小的答案。
而且左右對稱的位置只需要檢查到中間附近就夠了，不需要把整個字串都掃完。
所有變數
m：要檢查到的位置上限，我這裡設成(s.size() + 1) / 2n：字串長度
🪜 主要流程步驟
1. 先算出字串長度和檢查範圍
我先用 n 記住字串長度，這樣後面比較容易寫右邊對應位置。
接著我算出：
int m = (s.size() + 1) / 2;
這代表我最多只需要檢查到中間附近。 因為題目比較的是左右對稱位置，所以超過中間之後，其實就是在重複檢查前面做過的事情。
2. 從小到大枚舉每個可能的 i
我用一個 for 迴圈，從 0 開始一路往後試：
for (int i = 0; i <= m; i++) {
因為題目要的是最小的符合條件的索引， 所以這樣由小到大檢查，只要一找到答案，就可以直接回傳，不用再繼續往後看。
3. 檢查左右對稱位置的字元是否相同
在每個 i，我都比較：
s[i] == s[n - i - 1]
這個意思是：
- 左邊第
i個位置 - 和右邊對稱過來的位置
如果兩個字元一樣，就表示這個 i 已經符合題目要求。
所以我直接：
return i;
因為目前是從小到大掃過來的，第一個符合條件的 i 就一定是最小答案。
4. 如果整段都找不到，就回傳 -1
如果迴圈跑完都沒有任何一次符合：
s[i] == s[n - i - 1]
那就代表不存在合法的索引。 所以最後直接回傳 -1。
⏱️ 複雜度
設 n = s.length。
- 時間複雜度：
O(n)
最多只會從兩端往中間檢查一半左右的位置，仍然可以記成 O(n)。
- 空間複雜度：
O(1)
只用了固定數量的變數。
💻 程式碼實作
class Solution {
public:
int firstMatchingIndex(string s) {
int m = (s.size() + 1) / 2;
int n = s.size();
for (int i = 0; i <= m; i++) {
if (s[i] == s[n - i - 1]) {
return i;
}
}
return -1;
}
};
🔗 題目連結
https://leetcode.com/contest/weekly-contest-495/problems/first-matching-character-from-both-ends/