题目：【经典算法】LeetCode 20:有效的括号(Java/C/Python3实现含注释说明,Easy)
- 作者简介：阿里非典型程序员一枚 ，记录在大厂的打怪升级之路。 一起学习Java、大数据、数据结构算法（公众号同名）
- ❤️觉得文章还不错的话欢迎大家点赞👍➕收藏⭐️➕评论，💬支持博主，记得点个大大的
关注，持续更新🤞
————————————————-
题目描述
给你两个字符串 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 。 提示： 1 <= haystack.length, needle.length <= 104 haystack 和 needle 仅由小写英文字符组成
原题：LeetCode 28. 找出字符串中第一个匹配项的下标
思路及实现
方式一：暴力匹配
思路
暴力匹配是一种直观的解决方案。我们从字符串s的第一个字符开始，逐个字符与子串t进行比较。如果找到一个匹配，就返回当前的索引。如果整个s都被遍历完了还没有找到匹配，则返回-1。
代码实现
Java版本
public class Solution { public int strStr(String s, String t) { int m = s.length(); int n = t.length(); for (int i = 0; i <= m - n; i++) { int j; for (j = 0; j < n; j++) { if (s.charAt(i + j) != t.charAt(j)) { break; } } if (j == n) { return i; } } return -1; } }
说明：
- 外部循环遍历字符串
s，内部循环遍历子串t。- 如果在内部循环中发现字符不匹配，则跳出内部循环。
- 如果内部循环正常结束（即
j == n），说明找到了一个匹配，返回当前的索引i。
C语言版本
#include <string.h> int strStr(char *s, char *t) { int m = strlen(s); int n = strlen(t); for (int i = 0; i <= m - n; i++) { int j; for (j = 0; j < n; j++) { if (s[i + j] != t[j]) { break; } } if (j == n) { return i; } } return -1; }
说明：
- C语言版本与Java版本逻辑相同，只是语法上有所不同。
Python3版本
class Solution: def strStr(self, s: str, t: str) -> int: m = len(s) n = len(t) for i in range(m - n + 1): if s[i:i+n] == t: return i return -1
说明：
- Python使用切片操作
s[i:i+n]来比较子串，更加简洁。
Golang版本
func strStr(s string, t string) int { m := len(s) n := len(t) for i := 0; i <= m-n; i++ { if s[i:i+n] == t { return i } } return -1 }
说明：
- Golang的字符串切片操作和Python类似，也很简洁。
复杂度分析
- 时间复杂度：O((m-n+1)n)，其中m是字符串
s的长度，n是子串t的长度。最坏情况下，s的每个子串都需要与t进行比较。 - 空间复杂度：O(1)，只使用了常量级别的额外空间。
方式二：KMP算法
思路
KMP算法（Knuth-Morris-Pratt算法）是一种高效的字符串匹配算法。它能在O(m+n)的时间复杂度内找出子串在字符串中的位置。KMP算法的关键在于利用已经部分匹配的信息，避免不必要的比较。
代码实现
Java版本
public class Solution { public int strStr(String s, String t) { if (t.isEmpty()) return 0; int[] lps = computeLPSArray(t); int i = 0; // index for s[] int j = 0; // index for t[] int m = s.length(); int n = t.length(); while (i < m) { if (s.charAt(i) == t.charAt(j)) { j++; i++; } if (j == n) { return i - j; } else if (i < m && s.charAt(i) != t.charAt(j)) { if (j != 0) j = lps[j - 1]; else i = i + 1; } } return -1; } private int[] computeLPSArray(String pat) { int M = pat.length(); int lps[] = new int[M]; int len = 0; // length of the previous longest prefix suffix int i = 1; lps[0] = 0; // lps[0] is always 0 // the loop calculates lps[i] for i = 1 to M-1 while (i < M) { if (pat.charAt(i) == pat.charAt(len)) { len++; lps[i] = len; i++; } else { if (len != 0) { len = lps[len - 1]; } else { lps[i] = 0; i++; } } } return lps; } }
说明：
computeLPSArray方法用于计算最长前缀后缀数组（LPS），这是KMP算法的关键部分。- 在主方法中，我们使用两个指针
i和j分别遍历字符串s和子串t。- 当发现字符不匹配时，利用LPS数组回溯
j指针，而不是简单地将i和j都重置为0。
C语言版本
#include <string.h> void computeLPSArray(char *pat, int M, int *lps) { int len = 0; // length of the previous longest prefix suffix int i = 1; lps[0] = 0; // lps[0] is always 0 while (i < M) { if (pat[i] == pat[len]) { len++; lps[i] = len; i++; } else { if (len != 0) { len = lps[len - 1]; } else { lps[i] = 0; i++; } } } } int KMPSearch(char *pat, char *txt) { int M = strlen(pat); int N = strlen(txt); int lps[M]; computeLPSArray(pat, M, lps); int i = 0; // index for txt[] int j = 0; // index for pat[] while (i < N) { if (pat[j] == txt[i]) { j++; i++; } if (j == M) { return i - j; j = lps[j - 1]; } else if (i < N && pat[j] != txt[i]) { if (j != 0) j = lps[j - 1]; else i = i + 1; } } return -1; } int strStr(char *s, char *t) { return KMPSearch(t, s); }
说明：
- C语言版本的KMP算法实现与Java版本逻辑相似，但语法和内存管理有所不同。
Python3版本
由于Python的字符串是不可变的，并且Python的标准库已经提供了高效的字符串匹配功能，通常不需要手动实现KMP算法。Python可以使用内置的find()方法或in运算符来查找子串。
class Solution: def strStr(self, s: str, t: str) -> int: return s.find(t)
说明：
find()方法返回子串在字符串中首次出现的索引，如果未找到则返回-1。
Golang版本
下面是Golang版本的KMP算法实现：
package main import ( "fmt" ) func computeLPSArray(pat string, M int) []int { lps := make([]int, M) len := 0 // length of the previous longest prefix suffix i := 1 lps[0] = 0 // lps[0] is always 0 for i < M { if pat[i] == pat[len] { len++ lps[i] = len i++ } else { if len != 0 { len = lps[len-1] } else { lps[i] = 0 i++ } } } return lps } func KMPSearch(pat string, txt string) int { M := len(pat) N := len(txt) lps := computeLPSArray(pat, M) i := 0 // index for txt j := 0 // index for pat for i < N { if pat[j] == txt[i] { j++ i++ } if j == M { return i - j } else if i < N && pat[j] != txt[i] { if j != 0 { j = lps[j-1] } else { i++ } } } return -1 } func strStr(s string, t string) int { return KMPSearch(t, s) } func main() { s := "hello world" t := "world" index := strStr(s, t) if index != -1 { fmt.Printf("Found substring '%s' at index: %d\n", t, index) } else { fmt.Printf("Substring '%s' not found\n", t) } }
说明：
- Golang版本的KMP算法实现与Java和C语言版本类似，主要区别在于语法和类型声明。
computeLPSArray函数计算最长前缀后缀数组。KMPSearch函数是KMP算法的核心实现，用于在文本字符串txt中查找模式字符串pat。strStr函数是对外暴露的接口，它调用了KMPSearch函数，并返回子串在文本中的索引。main函数是程序的入口点，它演示了如何使用strStr函数来查找子串并打印结果。
复杂度分析
对于朴素字符串匹配算法（Naive Search），时间复杂度为O((N-M+1)*M)，其中N是母串的长度，M是模式串的长度。空间复杂度为O(1)，因为它只使用了有限的变量来追踪匹配位置。
对于KMP算法，时间复杂度在最坏情况下是O(N+M)，其中N是母串的长度，M是模式串的长度。空间复杂度是O(M)，用于存储最长公共前后缀数组（LPS数组）。
对于标准库函数（如Go中的strings.Index），其时间复杂度和空间复杂度通常是由实现决定的，并且经过优化。在大多数情况下，这些函数使用高效算法，并且性能优于手动实现的简单算法。
总结
下面是朴素字符串匹配算法和KMP算法的特点总结表格：
| 方式 | 优点 | 缺点 | 时间复杂度 | 空间复杂度 |
| 朴素字符串匹配 | 实现简单 | 效率低，当模式串与母串不匹配时，需要多次比较 | O((N-M+1)*M) | O(1) |
| KMP算法 | 效率较高，通过预处理减少不必要的比较 | 实现相对复杂 | O(N+M) | O(M) |
标准库函数（如strings.Index） |
简洁易用，性能通常经过优化 | 依赖外部库，可能不是最灵活的选择 | 取决于实现 | 取决于实现 |
相似题目
以下是一些与字符串匹配算法相关的相似题目：
| 相似题目 | 难度 | 链接 |
| LeetCode 28. 实现 strStr() | 简单 | LeetCode链接 |
| LeetCode 76. 最小覆盖子串 | 困难 | LeetCode链接 |
| LeetCode 438. 找到字符串中所有字母异位词 | 中等 | LeetCode链接 |
| LeetCode 472. 连接词 | 困难 | LeetCode链接 |
| LeetCode 567. 字符串的排列 | 中等 | LeetCode链接 |
这些题目涉及字符串匹配、子串查找、异位词检测以及字符串排列等概念，可以帮助你进一步巩固和扩展对字符串处理算法的理解。
欢迎一键三连(关注+点赞+收藏)，技术的路上一起加油！！！代码改变世界
- 关于我：阿里非典型程序员一枚 ，记录在大厂的打怪升级之路。 一起学习Java、大数据、数据结构算法（公众号同名），回复暗号，更能获取学习秘籍和书籍等
