# 28. Implement strStr()

## 1.問題

* 實作strStr, 若找不到則回傳 -1

![](https://901207480-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LGKoChvN9am4__HCIRK%2F-LO5XvFzvoC0Z_Z5XYHc%2F-LO7FYFPruOfWlz5CwDu%2F%E8%9E%A2%E5%B9%95%E5%BF%AB%E7%85%A7%202018-10-06%20%E4%B8%8B%E5%8D%883.22.52.png?alt=media\&token=bd8fb01a-0b52-42ff-8040-dbbf89e0ac90)

\
2.想法 <a href="#id-2-xiang-fa" id="id-2-xiang-fa"></a>
-----------------------------------------------------

* 提問
* function header, parameter
* test input
* 說明想法
  * 當碰到相同字母時, 讓計數器增加
  * 當不同字母時, 索引值就是減去計數器
* 測試計算複雜度: O(n)

## **3.程式碼** <a href="#id-3-cheng-shi" id="id-3-cheng-shi"></a>

```
class Solution {
public:
    int strStr(string haystack, string needle) {
        if (haystack.empty() && needle.empty()) {
            return 0;
        }
        if (haystack.empty()) {
            return -1;
        }
        if (needle.empty()) {
            return 0;
        }
        
        int s1 = haystack.length(), s2 = needle.length();
        for (int i = 0; i < s1; i++) {
            if (haystack[i] = needle[0] &&
                haystack.substr(i, s2) == needle) {
                return i;
            }
        }
        
        return -1;
    }
};
```
