05 August 2008
Implement strStr().
Return the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack.
Example 1:
1
2
Input: haystack = "hello", needle = "ll"
Output: 2
Example 2:
1
2
Input: haystack = "aaaaa", needle = "bba"
Output: -1
Clarification:
What should we return when 1
needle
For the purpose of this problem, we will return 0 when 1
needle
在一个字符串中找另一个字符串第一次出现的位置，有以下两种边界情况：如果子字符串为空，则返回0；如果子字符串长度大于母字符串长度，则返回-1。
开始遍历母字符串，我们并不需要遍历整个母字符串，而是遍历到剩下的长度和子字符串相等的位置即可，这样可以稍微提高运算效率。对于遍历到的每一个字符，都遍历一遍子字符串，一个一个字符的对应比较，如果对应位置有不等的，则跳出循环，如果一直都没有跳出循环，则说明子字符串出现了，则返回起始位置即可。
至于KMP算法，需要了解下，看这个链接。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public int strStr(String haystack, String needle) {
if (needle == null || needle.length() == 0) {
return 0;
}
int m = haystack.length(), n = needle.length();
if (n > m) {
return -1;
}
for (int i = 0; i <= m - n; i++) {//注意这里是<=，想想比如n==1，那就可能检查到m的最后一位
int j = 0;
for (j = 0; j < n; j++) {
if (haystack.charAt(i+j) != needle.charAt(j)) {
break;//break里面的for循环
}
}
if (j == n) {//没有break
return i;
}
}
return -1;//没找到
}
}
用substring
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public int strStr(String haystack, String needle) {
if (needle == null || needle.length() == 0) {
return 0;
}
int len = needle.length();
char ch = needle.charAt(0);
for (int i = 0; i <= haystack.length()-len; i++) {
if (haystack.charAt(i) == ch) { //先比较下首字符，聊胜于无
String temp = haystack.substring(i, i + len);
if (temp.equals(needle)) {
return i;
}
}
}
return -1;
}
}
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
public String strStr(String haystack, String needle) {
//KMP algorithms
if(needle.equals("")) return haystack;
if(haystack.equals("")) return null;
char[] arr = needle.toCharArray();
int[] next = makeNext(arr);
for(int i = 0, j = 0, end = haystack.length(); i < end;){
if(j == -1 || haystack.charAt(i) == arr[j]){
j++;
i++;
if(j == arr.length) return haystack.substring(i - arr.length);
}
if(i < end && haystack.charAt(i) != arr[j]) j = next[j];
}
return null;
}
private int[] makeNext(char[] arr){
int len = arr.length;
int[] next = new int[len];
next[0] = -1;
for(int i = 0, j = -1; i + 1 < len;){
if(j == -1 || arr[i] == arr[j]){
next[i+1] = j+1;
if(arr[i+1] == arr[j+1]) next[i+1] = next[j+1];
i++;
j++;
}
if(arr[i] != arr[j]) j = next[j];
}
return next;
}