Leetcode 找出字符串中第一个匹配项的下标

算法思想：

1. 检查特殊情况：首先判断needle是否为空字符串。如果是空字符串，根据题意直接返回0，因为空子串默认在任何字符串的起始位置。

2. 获取字符串长度：定义m为haystack的长度，n为needle的长度，这样可以避免每次循环时重复计算长度。

3. 循环遍历主字符串：通过for循环遍历haystack的每个字符位置，从0到m - n。这里的m - n是为了确保在主字符串haystack中留下足够的空间容纳子串needle，避免越界。

4. 截取子串并比较：在每次循环中，截取haystack中从索引i开始、长度为n的子串，并与needle进行比较。通过substring(i, i + n)来获取子串，并使用equals方法判断是否相等。

5. 返回匹配的索引：如果找到匹配的子串，则返回当前索引i，表示needle在haystack中首次出现的位置。

6. 未找到返回-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;
    }
}

原文地址：https://blog.csdn.net/coldasice342/article/details/143696597

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！