导航
导航
文章目录
  1. 题目
  2. 翻译
    1. 方法一:API法
    2. 方法二:暴力破解法
    3. 方法三:KMP

LeetCode-28.Implement strStr()

题目

Implement strStr().

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

翻译

实现strStr()。
返回haystack中,needle出现的第一个下标,如果haystack不包含needle,返回-1。

方法一:API法

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

方法二:暴力破解法

从haystack的第一个字符作为开始,向后判断needle.length()位字符看是否相等。
直到遇到子串,或长度超出:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public class Solution {
public int strStr(String haystack, String needle) {
int hLen = haystack.length(), nLen = needle.length();
for (int i = 0; i <= hLen - nLen; i++) {
int lastIndex = 0;
while (lastIndex < nLen) {
if (haystack.charAt(i + lastIndex) != needle.charAt(lastIndex))
break;
lastIndex++;
}
if (lastIndex == nLen)
return i;
}
return -1;
}
}

另外一种更简洁写法:

1
2
3
4
5
6
7
8
9
10
11
12
13
public class Solution {
public int strStr(String haystack, String needle) {
int hIndex = 0, nIndex = 0;
while (true) {
if (nIndex == needle.length()) return hIndex;
if (hIndex + nIndex == haystack.length()) return -1;
if (haystack.charAt(hIndex + nIndex) != needle.charAt(nIndex)) {
hIndex++;
nIndex = 0;
} else nIndex++;
}
}
}

但是效率最低……

方法三:KMP

参考:
http://www.programcreek.com/2012/12/leetcode-implement-strstr-java/
http://www.2cto.com/kf/201411/355542.html