# 28. Implement strStr()

### Leetcode

<https://leetcode.com/problems/implement-strstr/>

### 題目

Implement [strStr()](http://www.cplusplus.com/reference/cstring/strstr/).

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

**Clarification:**

What should we return when `needle` is an empty string? This is a great question to ask during an interview.

For the purpose of this problem, we will return 0 when `needle` is an empty string. This is consistent to C's [strstr()](http://www.cplusplus.com/reference/cstring/strstr/) and Java's [indexOf()](https://docs.oracle.com/javase/7/docs/api/java/lang/String.html#indexOf\(java.lang.String\)).

### 解答 <a href="#ti-jie" id="ti-jie"></a>

* **方法一**

```
var strStr = function(haystack, needle) {
    if(needle === "") return 0;
    
    for(let i=0; i<haystack.length-needle.length+1; i++) {
        let matchIndex = i;
        let j = 0;
        
        while(j < needle.length && haystack[matchIndex] === needle[j]) {
            matchIndex++;
            j++;
        }
        if (j === needle.length) return i;
    }
    return -1;
};
```

Runtime: 1064 ms, faster than 33.42% of JavaScript online submissions for Implement strStr().

Memory Usage: 41 MB, less than 11.06% of JavaScript online submissions for Implement strStr().

### 測資

```
let haystack = "hello", needle = "ll";
haystack = "aaaaa", needle = "bba";
haystack = "", needle = "";

console.log(strStr(haystack, needle));
```
