# LeetCode 28. Implement strStr()

## 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 * 104`
• `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).

## One Thought to “LeetCode 28. Implement strStr()”

1. Bala says:

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