当前位置：首页 > news >正文

刷题重开：找出字符串中第一个匹配项的下标——解题思路记录

news 2025/8/2 20:54:50

问题描述：

给你两个字符串 haystack 和 needle ，请你在 haystack 字符串中找出 needle 字符串的第一个匹配项的下标（下标从 0 开始）。如果 needle 不是 haystack 的一部分，则返回 -1 。

示例 1：

输入：haystack = "sadbutsad", needle = "sad"
输出：0
解释："sad" 在下标 0 和 6 处匹配。
第一个匹配项的下标是 0 ，所以返回 0 。

示例 2：

输入：haystack = "leetcode", needle = "leeto"
输出：-1
解释："leeto" 没有在 "leetcode" 中出现，所以返回 -1 。

解题思路：

简单方法

class Solution {public int strStr(String haystack, String needle) {return haystack.indexOf(needle);}
}

利用现成的方法，indexOf方法就是返回匹配的第一个字符串的索引位置

看一下源码（一环套一环）：

public int indexOf(int ch, int fromIndex) {final int max = value.length;if (fromIndex < 0) {fromIndex = 0;} else if (fromIndex >= max) {// Note: fromIndex might be near -1>>>1.return -1;}if (ch < Character.MIN_SUPPLEMENTARY_CODE_POINT) {// handle most cases here (ch is a BMP code point or a// negative value (invalid code point))final char[] value = this.value;for (int i = fromIndex; i < max; i++) {if (value[i] == ch) {return i;}}return -1;} else {return indexOfSupplementary(ch, fromIndex);}}

暴力方法

初始化变量：
- haystack：要搜索的字符串。
- needle：要查找的子字符串。
- haystackLength：haystack的长度。
- needleLength：needle的长度。
- result：用于存储匹配项的下标，初始化为-1（表示未找到）。
遍历haystack：
- 使用一个循环遍历haystack，从索引0开始，直到haystackLength - needleLength（因为从当前位置开始，如果剩余长度小于needle的长度，则不可能匹配）。
检查匹配：
- 在每次循环中，从当前索引开始，比较haystack和needle的字符，直到匹配完整个needle或发现不匹配。
- 如果发现完全匹配，则更新result为当前索引，并跳出循环（因为我们只需要找到第一个匹配项）。

返回结果：

如果找到匹配项，则返回result。

否则，返回-1。

public class StringMatcher {public static int strStr(String haystack, String needle) {int haystackLength = haystack.length();int needleLength = needle.length();if (needleLength == 0) {return 0; // 如果needle为空字符串，则任何位置都是匹配项，返回0（根据题意）}for (int i = 0; i <= haystackLength - needleLength; i++) {int j;for (j = 0; j < needleLength; j++) {if (haystack.charAt(i + j) != needle.charAt(j)) {break; // 一旦发现不匹配，跳出内层循环}}if (j == needleLength) {return i; // 如果完全匹配，返回当前索引}}return -1; // 未找到匹配项，返回-1}public static void main(String[] args) {String haystack = "hello haystack";String needle = "stack";int index = strStr(haystack, needle);System.out.println("The first occurrence of \"" + needle + "\" in \"" + haystack + "\" is at index: " + index);}
}

代码解释：

外层循环

for (int i = 0; i <= haystackLength - needleLength; i++)

这个循环从haystack的第一个字符开始，直到haystack中剩余字符的数量不足以匹配整个needle为止。
变量i代表当前正在检查的haystack中的起始位置。
条件i <= haystackLength - needleLength 确保了 i + needleLength 不会超过 haystack的长度，从而避免 StringIndexOutOfBoundsException。
体会一下，比如第一个字符串是234523,第二个字符串是23。那只需要外层循环6-2=4（次）