LeetCode-找出字符串中第一个匹配项的下标（028）

一.题目描述

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

示例 1：

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

复制代码

示例 2：

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

复制代码

三.提示：

• 1 <= haystack.length, needle.length <= 104
  
• haystack 和 needle 仅由小写英笔墨符构成
  

四.解法:

方法一：遍历

以字符串 haystack 的每一个字符为起点与字符串 needle 进行比力，若发现可以大概匹配的索引，直接返回即可。
假设字符串 haystack 长度为 n，字符串 needle 长度为 m，则时间复杂度为 O((n−m)×m)，空间复杂度 O(1)。
五.代码

Java代码

1. class Solution {
2.     public int strStr(String haystack, String needle) {
3.         // 如果 needle 是空字符串，返回 0
4.         if ("".equals(needle)) {
5.             return 0;
6.         }
8.         // 获取 haystack 和 needle 的长度
9.         int len1 = haystack.length();
10.         int len2 = needle.length();
11.         
12.         // 初始化指针 p 和 q
13.         int p = 0;
14.         int q = 0;
15.         
16.         // 遍历 haystack
17.         while (p < len1) {
18.             // 如果当前字符匹配
19.             if (haystack.charAt(p) == needle.charAt(q)) {
20.                 // 如果 needle 只有一个字符，返回当前索引
21.                 if (len2 == 1) {
22.                     return p;
23.                 }
24.                 // 移动指针 p 和 q
25.                 ++p;
26.                 ++q;
27.             } else {
28.                 // 如果不匹配，回退 p 指针，并重置 q 指针
29.                 p -= q - 1;
30.                 q = 0;
31.             }
33.             // 如果 q 达到 needle 的长度，说明找到了匹配
34.             if (q == len2) {
35.                 return p - q;
36.             }
37.         }
38.         
39.         // 如果没有找到匹配，返回 -1
40.         return -1;
41.     }
42. }
44. 注释说明
45.     ·空字符串检查：如果 needle 是空字符串，直接返回 0。
46.     ·长度获取：len1 和 len2 分别表示 haystack 和 needle 的长度。
47.     ·指针初始化：p 用于遍历 haystack，q 用于遍历 needle。
48.     ·遍历和匹配：
49.         ·如果 haystack 的当前字符与 needle 的当前字符匹配，移动 p 和 q。
50.         ·如果 needle 只有一个字符且匹配，立即返回当前索引 p。
51.         ·如果字符不匹配，回退 p 指针到上一次匹配的下一个位置，并重置 q。
52.     ·匹配成功：如果 q 达到 needle 的长度，返回匹配的起始索引 p - q。
53.     ·返回结果：如果遍历结束没有找到匹配，返回 -1。

复制代码