題目

題目翻譯

給一個指針needle跟字串堆疊haystack，回傳指針第一次在堆疊中出現的位置index

解題思路

這題要求實現 strStr() 函數，該函數的作用是找到字串 needle 在字串 haystack 中首次出現的位置。如果 needle 不存在於 haystack 中，則返回 -1。這相當於實現一個子字串搜索功能。

思路：

1. 字串查找：可以直接使用 C++ 標準庫中的 find() 函數來查找 needle 在 haystack 中的第一次出現位置。這是最簡單且高效的做法，因為 find() 函數已經為我們優化了搜索過程。

2. 返回結果：

   • 如果 find() 找不到 needle，會返回 string::npos，這是標準庫用來表示查找失敗的特殊值。
   • 如果找到 needle，find() 會返回 needle 在 haystack 中的起始索引。

3. 處理邊界情況：

   • 如果 needle 是空字串，根據題目要求，應返回 0。這是因為一個空字串可以被認為在任何字串的起始位置出現。
   • 如果 haystack 或 needle 都是空字串，應根據邏輯適當處理。

改進的程式碼

class Solution {
public:
    int strStr(string haystack, string needle) {
        // 邊界條件: 如果 needle 是空字串，返回 0
        if (needle.empty()) return 0;
        
        // 使用 find 函數尋找 needle 的第一次出現位置
        size_t pos = haystack.find(needle);
        
        // 如果找不到，返回 -1，否則返回找到的位置
        return pos == string::npos ? -1 : static_cast<int>(pos);
    }
};

解題步驟

1. 檢查邊界條件：

   • 首先檢查 needle 是否為空字串，如果是，根據題目要求直接返回 0。

2. 使用 find() 搜索子字串：

   • 調用 haystack.find(needle)，它會返回 needle 在 haystack 中的第一個出現位置，或者返回 string::npos（表示沒找到）。

3. 處理搜索結果：

   • 如果結果是 string::npos，意味著 needle 沒有在 haystack 中出現，返回 -1。
   • 否則，返回 needle 的起始位置。

時間與空間複雜度

• 時間複雜度：O(m * n)（最壞情況），其中 m 是 haystack 的長度，n 是 needle 的長度。標準庫的 find() 函數可能已經對搜索過程進行了優化，但最壞情況下依然需要檢查每一個位置。

• 空間複雜度：O(1)，因為我們只使用了常數額外空間。