# Implement strStr()

Implement strStr().

Return the index of the first occurrence of needle in haystack, or-1if 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().

## Analysis

O(n^2) time, O(1) space

KMP算法

## Solution

### Two loops

``````public int strStr(String s, String t) {
if (t.isEmpty()) return 0; // edge case: "",""=>0  "a",""=>0
for (int i = 0; i <= s.length() - t.length(); i++) {
for (int j = 0; j < t.length() && s.charAt(i + j) == t.charAt(j); j++)
if (j == t.length() - 1) return i;
}
return -1;
}``````

### Use needle as pattern string, outer loop move n - m + 1 times, inner loop at most m times

``````class Solution {
public int strStr(String haystack, String needle) {
if (needle.isEmpty()) {
return 0;
}
if (haystack == null || haystack.isEmpty()) {
return -1;
}
int n = haystack.length();
int m = needle.length();

for (int i = 0; i < n - m + 1; i++) {
if (matches(haystack.substring(i, i + m), needle)) {
return i;
}
}

return -1;
}
private boolean matches(String s, String t) {
if (s.length() != t.length()) {
return false;
}
int len = s.length();
for (int i = 0; i < len; i++) {
if (s.charAt(i) != t.charAt(i)) {
return false;
}
}
return true;
}
}``````

### Multiple Pointers - O(mn) time

``````public class Solution {
/**
* @param source:
* @param target:
* @return: return the index
*/
public int strStr(String source, String target) {
if (target.equals("")){
return 0;
}
for (int i = 0; i < source.length() - target.length() + 1; i++){
int j = 0;
int k = i;
while (j < target.length() && k < source.length()){
if (source.charAt(k) == target.charAt(j)){
k++;
j++;
} else {
break;
}
}
if(j == target.length()){
return k - target.length();
}
}
return -1;
}
}``````

### Using string equals

``````public int strStr(String haystack, String needle) {
if(needle.equals("")) return 0;
int L = needle.length();
for(int i=0; i<=haystack.length()-L; i++)
if(haystack.substring(i,i+L).equals(needle)) return i;
return -1;
}``````

Last updated