算法练习——实现 strStr()

2021年1月25日算法练习为28. 实现 strStr(),实现这个算法只需要找到头对应的位置,然后开始逐个字符对比即可。当needlle为null或者为空字符的时候返回符合业务期望的返回值即可,题设中指定返回0。当逐字符比较的时候发现有一个字符没有匹配上,则将cur指针归0,方便下一次比较,配对成功的条件为指针curneedle的长度大小时,说明匹配已经完成了,只需要返回当前的i就是这个needle匹配上的最前位置。如果扫描的时候发现needle的长度大于剩下的字符长度,说明后面的扫描已经没有必要进行下去,结束并返回。

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 || "".equals(needle)) {
return 0;
}
int cur = 0;
char[] strs = haystack.toCharArray();
char[] targets = needle.toCharArray();
for (int i = 0; i < strs.length; i++) {
if (strs.length - i < targets.length) return -1;
if (strs[i] == targets[cur]) {
for (int j = i; j < strs.length && cur < targets.length; j++) {
if (strs[j] != targets[cur++]) {
cur = 0;
break;
}
}
if (cur == targets.length) return i;
}
}
return -1;
}
}