Topic

Two Pointers, String

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.

needle /?ni?dl/ n.針

haystack /?he?st?k/ n.干草堆

a needle in a haystack：something that is impossible or extremely difficult to find, especially because the area you have to search is too large（類似中文的“大海撈針”）:

Finding the piece of paper I need in this huge pile of documents is like looking for/trying to find a needle in a haystack。

Link

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.

Analysis

方法一：雙指針

方法二：KMP算法

Submission

public class ImplementStrStr {public int strStr(String haystack, String needle) {for (int i = 0;; i++) {for (int j = 0;; j++) {if (j == needle.length())return i;if (i + j == haystack.length())return -1;if (needle.charAt(j) != haystack.charAt(i + j))break;}}}private void getNext(int[] next, String s) {int j = -1;next[0] = j;for(int i = 1; i < s.length(); i++) { // 注意i從1開始while (j >= 0 && s.charAt(i) != s.charAt(j + 1)) { // 前后綴不相同了j = next[j]; // 向前回溯}if (s.charAt(i) == s.charAt(j + 1)) { // 找到相同的前后綴j++;}next[i] = j; // 將j（前綴的長度）賦給next[i]}}public int strStr2(String haystack, String needle) {if (needle.length() == 0) {return 0;}int[] next = new int[needle.length()];getNext(next, needle);int j = -1; // // 因為next數組里記錄的起始位置為-1for (int i = 0; i < haystack.length(); i++) { // 注意i就從0開始while(j >= 0 && haystack.charAt(i) != needle.charAt(j + 1)) { // 不匹配j = next[j]; // j 尋找之前匹配的位置}if (haystack.charAt(i) == needle.charAt(j + 1)) { // 匹配，j和i同時向后移動 j++; }if (j == (needle.length() - 1) ) { // 文本串s里出現了模式串treturn (i - needle.length() + 1); }}return -1;}}

Test

import static org.junit.Assert.*;
import org.junit.Test;public class ImplementStrStrTest {@Testpublic void test() {ImplementStrStr obj = new ImplementStrStr();assertEquals(2, obj.strStr("hello", "ll"));assertEquals(-1, obj.strStr("aaaaaa", "bba"));assertEquals(0, obj.strStr("", ""));assertEquals(-1, obj.strStr("aaa", "aaaa"));}@Testpublic void test2() {ImplementStrStr obj = new ImplementStrStr();assertEquals(2, obj.strStr2("hello", "ll"));assertEquals(-1, obj.strStr2("aaaaaa", "bba"));assertEquals(0, obj.strStr2("", ""));assertEquals(-1, obj.strStr2("aaa", "aaaa"));}
}