# LeetCode Solution, Easy, 28. Implement strStr()

# [28. Implement strStr()](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.

**Example 1:**

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

**Example 2:**

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

**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()` and Java's `indexOf()`.

**Constraints:**

- `haystack` and `needle` consist only of lowercase English characters.

### 題目翻譯

這個題目其實就是要實作出子字串索引的搜尋函數。找出子字串開頭的索引，如果不包含子字串就回傳 `0`。

## 解法解析

基本的解法邏輯參考 Go 的範例，其他語言算是偷懶。因為題目是要實作出函數，所以直接使用程式語言的 built-in 函數，算是偷吃步，正確方式應該像是 Go 的範例。使用類似 Sliding window 的方式去比對。

### 解法範例

#### Go

```go
func strStr(haystack string, needle string) int {
	if haystack == needle {
		return 0
	}
	for i := 0; i <= len(haystack)-len(needle); i++ {
		if haystack[i:i+len(needle)] == needle {
			return i
		}
	}

	return -1
}
```

#### JavaScript

```javascript
/**
 * @param {string} haystack
 * @param {string} needle
 * @return {number}
 */
var strStr = function (haystack, needle) {
    if (needle.length === 0) return 0;
    return haystack.indexOf(needle);
};
```

#### Kotlin

```kotlin
class Solution {
    fun strStr(haystack: String, needle: String): Int {
        if (needle.isEmpty()) return 0
        return haystack.indexOf(needle)
    }
}
```

#### PHP

```php
class Solution
{

    /**
     * @param String $haystack
     * @param String $needle
     * @return Integer
     */
    function strStr($haystack, $needle)
    {
        return strpos($haystack, $needle) !== false ? strpos($haystack, $needle) : -1;
    }
}
```

#### Python

```python
class Solution:
    def strStr(self, haystack: str, needle: str) -> int:
        if needle in haystack:
            return haystack.index(needle)
        return -1
```

#### Rust

```rust
```

#### Swift

```swift
class Solution {
    func strStr(_ haystack: String, _ needle: String) -> Int {
        guard !needle.isEmpty else { return 0 }
        guard haystack.count >= needle.count else { return -1 }

        let distance = haystack.count - needle.count
        for i in 0...distance {
            let start = haystack.index(haystack.startIndex, offsetBy: i)
            let end = haystack.index(haystack.startIndex, offsetBy: i+needle.count)

            if haystack[start..<end] == needle {
                return start.encodedOffset
            }
        }
        return -1
    }
}
```