LeetCode - Algorithms - 28. Implement strStr()

Java

1 KMP algorithm

北京大学信息科学与技术学院《数据结构与算法》 之 KMP模式匹配算法 ©版权所有

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
class Solution {
	public int[] nextVector(String P) {
		int[] arr = new int[P.length()];
		arr[0] = 0;
		int k = 0;
		for (int i = 1; i < P.length(); i++) {
			k = arr[i - 1];

			while (k > 0 && P.charAt(i) != P.charAt(k)) {
				k = arr[k - 1];
			}

			if (P.charAt(i) == P.charAt(k))
				arr[i] = k + 1;
			else
				arr[i] = 0;
		}
		return arr;
	}

	public int findPat_KMP(String S, String P, int[] N, int startIndex) {
		int lastIndex = S.length() - P.length();
		if (lastIndex < startIndex)
			return -1;
		int i = startIndex, j = 0;
		for (; i < S.length(); i++) {
			while (P.charAt(j) != S.charAt(i) && j > 0)
				j = N[j - 1];
			if (S.charAt(i) == P.charAt(j))
				j++;
			if (j == P.length())
				return i - j + 1;
		}
		return -1;
	}    

    public int strStr(String haystack, String needle) {
        if (needle.isEmpty()) return 0;
    	int[] arr = nextVector(needle);
    	if (needle.isEmpty()) return 0;
        return findPat_KMP(haystack,needle,arr,0);        
    }
}

Submission Detail

  • 74 / 74 test cases passed.
  • Runtime: 9 ms, faster than 26.57% of Java online submissions for Implement strStr().
  • Memory Usage: 38.5 MB, less than 0.98% of Java online submissions for Implement strStr().

2 JDK String indexOf

1
2
3
4
5
6
class Solution {
    public int strStr(String haystack, String needle) {
    	if (needle.isEmpty()) return 0;
        return haystack.indexOf(needle);        
    }
}

Submission Detail

  • 74 / 74 test cases passed.
  • Runtime: 3 ms, faster than 99.58% of Java online submissions for Implement strStr().
  • Memory Usage: 38.1 MB, less than 0.98% of Java online submissions for Implement strStr().