算法：实现strStr()，字符串indexOf方法

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

描述

给定一个 haystack 字符串和一个 needle 字符串，在 haystack 字符串中找出 needle 字符串出现的第一个位置 (从0开始)。如果不存在，则返回 -1。

个人思路：

思路一：当然先想到java中的indexOf方法。不过既然是算法题，那还是自己写一个出来。

思路二：判断字符串为空指针或者空字符串直接先返回，在将字符串转换成字符数组，单层循环，判断needle字符串的第一个与haystack第n个匹配，则通过数组拷贝copyOfRange将第一个数组拷出与第二个数组指定长度的数组，在用Arrays.toString()方法转换成字符串比较。

class Solution {
public int strStr(String haystack, String ll) {
// 判断空字符和空指针
if (haystack == null || ll == null) {
return -1;
}
if (ll.length() == 0) {
return 0;
}
// 转换为字符数组
char[] charArray = haystack.toCharArray();
char[] charArray2 = ll.toCharArray();
char[] temp = null;
// 循环遍历查询匹配值
for(int i = 0; i < charArray.length; ++i) {
// 判断第一个字符是否相等，并且剩余长度是否满足第二个字符串
if (charArray[i] == charArray2[0] && i + charArray2.length <= charArray.length) {
// 拷贝指定下标长度等于needle的数组
temp = Arrays.copyOfRange(charArray, i, i + charArray2.length);
// 转换为字符串进行比较，成功返回当前下标
if (Arrays.toString(charArray2).equals(Arrays.toString(temp))) {
return i;
}
}
} return -1;
}
}

缺陷很明显，字符串转换数组，拷贝，又转换为字符串。消耗内存和时间。

思路三：双重循环比较匹配字符

// 前面字符串转换一样
boolean check = false;
for(int i = 0; i < charArray.length; ++i) {
if (charArray[i] == charArray2[0] && i + charArray2.length <= charArray.length) {
check = true;
for(int j = 0; j < charArray2.length; ++j) {
if (charArray[i + j] != charArray2[j]) {
check = false;
}
}
if (check) {
return i;
}
}
}

效率高了不少

大神思路：

KMP算法。减少重复匹配次数，使用数组存储needle字符状态（默认状态为0，初始化第一个字符所在位置的状态为1，后面每一个字符所在位置的状态都会+1，并拷贝上一个状态列的字符状态，重置状态为当前字符所在位置的值），之后遍历kaystack字符串，直到匹配的状态与needle长度一致为止，否则返回-1，但更耗时

class Solution {
public int strStr(String haystack, String needle) { if (haystack == null || needle == null) {
return -1;
}
if (needle.length() == 0) {
return 0;
} int[][] dp = null;
int length = needle.length(); dp = new int[length][256];
dp[0][needle.charAt(0)] = 1;
int x = 0;
for(int i = 1; i < length; ++i) {
for(int j = 0; j < 256; ++j) {
if (j == needle.charAt(i)) {
dp[i][j] = i+1;
}else {
dp[i][j] = dp[x][j];
}
}
x = dp[x][needle.charAt(i)];
} int j = 0;
for(int i = 0; i < haystack.length(); ++i) {
j = dp[j][haystack.charAt(i)];
if (j == length) {
return i - length + 1;
}
}
return -1;
}
}