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

问题描述： 

给你两个字符串 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);}}

暴力方法

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

内层循环

	for (j = 0; j < needleLength; j++) {
	if (haystack.charAt(i + j) != needle.charAt(j))

• 这个循环用于逐个字符地比较haystack从位置i开始的子字符串和needle。
• 变量j代表当前正在比较的字符的索引。
• 如果在任何时候haystack中的字符与needle中的对应字符不匹配，break语句会立即终止内层循环。

还有KMP算法，但是不会用，后面慢慢学习！