算法思想:
-
检查特殊情况:首先判断
needle
是否为空字符串。如果是空字符串,根据题意直接返回0
,因为空子串默认在任何字符串的起始位置。 -
获取字符串长度:定义
m
为haystack
的长度,n
为needle
的长度,这样可以避免每次循环时重复计算长度。 -
循环遍历主字符串:通过
for
循环遍历haystack
的每个字符位置,从0
到m - n
。这里的m - n
是为了确保在主字符串haystack
中留下足够的空间容纳子串needle
,避免越界。 -
截取子串并比较:在每次循环中,截取
haystack
中从索引i
开始、长度为n
的子串,并与needle
进行比较。通过substring(i, i + n)
来获取子串,并使用equals
方法判断是否相等。 -
返回匹配的索引:如果找到匹配的子串,则返回当前索引
i
,表示needle
在haystack
中首次出现的位置。 -
未找到返回-1:如果循环结束都未找到匹配的子串,返回
-1
,表示needle
不在haystack
中。
复杂度分析
- 时间复杂度:在最坏情况下,算法需要遍历
haystack
的每个字符,因此时间复杂度是O((m - n + 1) * n)
,即O(m * n)
,其中m
是haystack
的长度,n
是needle
的长度。 - 空间复杂度:使用了常数空间,只在循环中存储了一些变量,因此空间复杂度为
O(1)
。
这个算法相对简单、直观,适用于needle
和haystack
长度不特别大的情况。
java 实现
class Solution {public int strStr(String haystack, String needle) {int m = haystack.length();int n = needle.length();if(n == 0) return 0;for(int i = 0; i <= m - n; i++) {String substr = haystack.substring(i, i + n);if(substr.equals(needle)) {return i;}}return -1;}
}