## Description

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

Implement 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() and Java’s indexOf().

**Example 1:**

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

**Example 2:**

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

**Example 3:**

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

**Constraints:**

`0 <= haystack.length, needle.length <= 5 * 10`

^{4}`haystack`

and`needle`

consist of only lower-case English characters.

## Explanation

The problem is asking for the index of the first occurrence of *needle* in *haystack.*

The idea to solve the problem is that we check whether is able to loop through each character of *needle* from one position of *haystack*.

## Java Solution

```
public class Solution {
public int strStr(String haystack, String needle) {
if (haystack == null || needle == null) {
return -1;
}
for (int i = 0; i < haystack.length() - needle.length() + 1; i++) {
int j;
for (j = 0; j < needle.length(); j++) {
if (haystack.charAt(i + j) != needle.charAt(j)) {
break;
}
}
if (j == needle.length()) {
return i;
}
}
return -1;
}
}
```

## Python Solution

```
class Solution:
def strStr(self, haystack: str, needle: str) -> int:
if len(needle) > len(haystack):
return -1
for i in range(0, len(haystack) - len(needle) + 1):
j = 0
while j < len(needle):
if haystack[i + j] != needle[j]:
break
j += 1
if j == len(needle):
return i
return -1
```

- Time Complexity:

- Time complexity: O(M – N), where M is the length of the haystack and N is the length of the needle. We compute a substring of length L in a loop, which is executed (M – N) times.
- Space complexity: O(1).

i appreciate your work very nice explanation i have subscribed to youtube channel,it would be very helpful if we have test cases attached 🙂