# 28\_Implement strStr()

\[Easy]

Return the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack.

**Example 1**

```
Input: haystack = "hello", needle = "ll"
Output: 2
```

**Example 2**

```
Input: haystack = "aaaaa", needle = "bba"
Output: -1
```

**Example 3 (need to pay attention)**

```
Input: haystack = "hello", needle = ""
Output: 0
```

**Example 4 (need to pay attention)**

```
Input: haystack = "", needle = "ll"
Output: -1
```

**Example 5 (need to pay attention)**

```
Input: haystack = "", needle = ""
Output: 0
```

**Example 6 (need to pay attention)**

```
Input: haystack = "a", needle = "abc"
Output: -1
```

## Solution 1: _Sliding Window 滑动窗口_

_**Idea**:_&#x20;

* This is a clean brute-force algorithm. We can traverse all the possible starting points of `haystack`(from `0`to

`haystack.length() - needle.length()`) and see if the following characters in `haystack`match those of `needle`.

**Special cases**:

* Both `haystack` and `needle` can be empty. If `haystack` is empty, `needle` is not, should return `-1`. If `needle` is empty, `haystack` is not, should return `0`. If both empty, should return `0`.

**Time complexity**: $$O((n-k)k)$$, where `k` is the number of characters in `needle.`

**Code 1**:

```python
class Solution(object):
    def strStr(self, haystack, needle):
        """
        :type haystack: str
        :type needle: str
        :rtype: int
        """
        for i in range(len(haystack) - len(needle)+1):
            if haystack[i:i+len(needle)] == needle:
                return i
        return -1
```

**Code 2:**

```python
class Solution(object):
    def strStr(self, haystack, needle):
        """
        :type haystack: str
        :type needle: str
        :rtype: int
        """
        if len(needle) == 0:
            return 0
        if len(haystack) == 0:
            return -1
        for i in range(len(haystack) - len(needle) + 1):
            for j in range(len(needle)):
                if haystack[i + j] != needle[j]:
                    break
            else:                                # when no break is triggered in the previous for loop
                return i
        return -1
```
