3884. First Matching Character From Both Ends

📘 題目敘述

給定一個長度為 n 的字串 s，內容只包含小寫英文字母。

請回傳最小的索引 i，使得：

• s[i] == s[n - i - 1]

如果不存在這樣的索引，回傳 -1。

條件限制

• 1 <= n == s.length <= 100
• s 只包含小寫英文字母

🧠 解題思路

我這題的想法很直接，就是從字串兩端往中間檢查。

因為題目要找的是最小的 i，滿足：

• 左邊是 s[i]
• 右邊對應位置是 s[n - i - 1]

所以我只要從小到大枚舉 i，每次檢查這兩個位置的字元有沒有一樣。 只要第一次出現一樣，我就可以立刻回傳，因為那一定就是最小的答案。

而且左右對稱的位置只需要檢查到中間附近就夠了，不需要把整個字串都掃完。

所有變數

• m：要檢查到的位置上限，我這裡設成 (s.size() + 1) / 2
• n：字串長度

🪜 主要流程步驟

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/problems/first-matching-character-from-both-ends/