【经典算法】LeetCode28 找出字符串中第一个匹配项的下标(Java/C/Python3实现含注释说明,Easy)

简介: 【经典算法】LeetCode28 找出字符串中第一个匹配项的下标(Java/C/Python3实现含注释说明,Easy)

题目:【经典算法】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算法的关键部分。
  • 在主方法中,我们使用两个指针ij分别遍历字符串s和子串t
  • 当发现字符不匹配时,利用LPS数组回溯j指针,而不是简单地将ij都重置为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、大数据、数据结构算法(公众号同名),回复暗号,更能获取学习秘籍和书籍等

相关文章
|
13天前
|
自然语言处理 算法 搜索推荐
字符串相似度算法完全指南:编辑、令牌与序列三类算法的全面解析与深入分析
在自然语言处理领域,人们经常需要比较字符串,这些字符串可能是单词、句子、段落甚至是整个文档。如何快速判断两个单词或句子是否相似,或者相似度是好还是差。这类似于我们使用手机打错一个词,但手机会建议正确的词来修正它,那么这种如何判断字符串相似度呢?本文将详细介绍这个问题。
182 1
|
15天前
|
数据采集 算法 JavaScript
揭开JavaScript字符串搜索的秘密:indexOf、includes与KMP算法
JavaScript字符串搜索涵盖`indexOf`、`includes`及KMP算法。`indexOf`返回子字符串位置,`includes`检查是否包含子字符串。KMP是高效的搜索算法,尤其适合长模式匹配。示例展示了如何在数据采集(如网页爬虫)中使用这些方法,结合代理IP进行安全搜索。代码示例中,搜索百度新闻结果并检测是否含有特定字符串。学习这些技术能提升编程效率和性能。
揭开JavaScript字符串搜索的秘密:indexOf、includes与KMP算法
|
13天前
|
语音技术 Python
语音识别,python字面量,注释,变量,python变量的格式是变量名 = 变量值,加减乘除的输入方式
语音识别,python字面量,注释,变量,python变量的格式是变量名 = 变量值,加减乘除的输入方式
|
3天前
|
Unix Linux Shell
Sphinx是一个Python文档生成工具,它可以解析reStructuredText或Markdown格式的源代码注释,并生成多种输出格式,如HTML、LaTeX、PDF、ePub等。
Sphinx是一个Python文档生成工具,它可以解析reStructuredText或Markdown格式的源代码注释,并生成多种输出格式,如HTML、LaTeX、PDF、ePub等。
6 0
|
28天前
|
Python
Python Google风格注释详解
Google风格注释是Python代码注释的一种标准化格式,它提供了一种规范的注释格式,使得代码更加易读、易于维护。Google风格注释使用三个双引号来包围注释内容,并按照一定规范编写。在注释中使用动词短语来描述函数的行为,并使用被动语态。在注释中使用正确的标点符号和缩进,使得注释易于阅读和理解。通过使用Google风格注释,我们可以为代码提供清晰的文档和说明,使得代码更加易读、易于维护。
31 3
|
28天前
|
Python
Python reStructuredText风格注释详解
reStructuredText风格注释是Python代码注释的一种标准化格式,它提供了一种规范的注释格式,使得代码更加易读、易于维护。reStructuredText风格注释使用两个等号来包围注释标题,并按照一定规范编写。通过使用reStructuredText风格注释,我们可以为代码提供清晰的文档和说明,使得代码更加易读、易于维护。
24 2
|
7天前
|
Python
155. 最小栈 力扣 python 空间换时间 o(1) 腾讯面试题
155. 最小栈 力扣 python 空间换时间 o(1) 腾讯面试题
|
7天前
|
存储 算法 索引
1124. 表现良好的最长时间段 (python) 前缀和 分类讨论 最大长度 力扣 面试题
1124. 表现良好的最长时间段 (python) 前缀和 分类讨论 最大长度 力扣 面试题
|
1月前
|
存储 算法 调度
力扣中级算法(Python)
力扣中级算法(Python)
|
1月前
|
算法 Python
力扣初级算法(Python)(二)
力扣初级算法(Python)(二)