# 028-implement-strstr

## Question

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

Implement strStr().

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

Example:

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

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

## Thought Process

1. Two Pointers
1. At each position, we simply compare the letter matches
2. Time complexity O(hn), where h is the length of haystack and n is length of needle
3. Space complexity O(1)

## Solution

``````class Solution {
public int strStr(String haystack, String needle) {
if(haystack.length() < needle.length()) return -1;
if(needle.length() == 0) return 0;
char[] hc = haystack.toCharArray();
char[] nc = needle.toCharArray();
int id = -1;
for(int i = 0; i <= hc.length - nc.length; i++){
if(match(hc, i, nc)){
return i;
}
}
return id;
}

public boolean match(char[] hc, int start, char[] nc){
for(int i = 0; i < nc.length; i++){
if(hc[start++] != nc[i]) return false;
}
return true;
}
}
``````