# 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.

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().

## 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.

Time Complexity: O((m – n + 1) * n) = O(m * n). m is the length of haystack. n is the length of needle.

## 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``````

## 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 🙂