LeetCode 28.找出字符串中第一个匹配项的下标
2024-01-03 16:37:46
找出字符串中第一个匹配项的下标
给你两个字符串 haystack 和 needle ,请你在 haystack 字符串中找出 needle 字符串的第一个匹配项的下标(下标从 0 开始)。如果 needle 不是 haystack 的一部分,则返回 -1 。
示例 1:
输入:haystack = “sadbutsad”, needle = “sad”
输出:0
解释:“sad” 在下标 0 和 6 处匹配。
第一个匹配项的下标是 0 ,所以返回 0 。
方法一、暴力法
类似双指针的思想,遍历解决。优势就是简单容易理解,但时间复杂度不是最优。
复杂度
时间复杂度:O(n*m)
空间复杂度:O(1)
Swift
func strStr(_ haystack: String, _ needle: String) -> Int {
let cntL = haystack.count
let cntR = needle.count
var i = 0
while i+cntR <= cntL {
var flag = true
for j in 0..<cntR {
if haystack[haystack.index(haystack.startIndex, offsetBy: i+j)] != needle[needle.index(needle.startIndex, offsetBy: j)] {
flag = false
break
}
}
if flag {
return i
}
i += 1
}
return -1
}
OC
-(NSInteger)strStr:(NSString *)haystack needle:(NSString *)needle {
if (needle.length <= 0) {
return -1;
}
NSInteger n = haystack.length, m = needle.length;
for (NSInteger i=0; i+m<=n; i++) {
NSInteger j = 0;
while (j<m && [haystack characterAtIndex:i+j] == [needle characterAtIndex:j]) {
j++;
}
if (j == m) {
return i;
}
}
return -1;
}
方法二、KMP算法(推荐)
面试的时候如果能撸出来,那么基本就稳了,相反,如果只知道暴力法,那可能结果就是回去等通知吧。
具体算法讲解请参考:
彻底搞懂KMP算法!!(配视频讲解)
Swift
//KMP 解法
func strStr(_ haystack: String, _ needle: String) -> Int {
let n = haystack.count
let m = needle.count
if m == 0 {
return 0
}
//构造next数组
var pi = Array(repeating: 0, count: m+1)
var j = 0
for i in 1..<m {
while j > 0 && needle[needle.index(needle.startIndex, offsetBy: i)] != needle[needle.index(needle.startIndex, offsetBy:j)] {
j = pi[j-1]
}
if needle[needle.index(needle.startIndex, offsetBy: i)] == needle[needle.index(needle.startIndex, offsetBy: j)] {
j += 1
}
pi[i] = j
}
j = 0
for i in 0..<n {
while j>0 && haystack[haystack.index(haystack.startIndex, offsetBy: i)] != needle[needle.index(needle.startIndex, offsetBy: j)] {
j = pi[j-1]
}
if haystack[haystack.index(haystack.startIndex, offsetBy: i)] == needle[needle.index(needle.startIndex, offsetBy: j)] {
j += 1
}
if j == m {
return i-m+1
}
}
return -1
}
OC
//KMP
-(NSInteger)strStr:(NSString *)haystack needle:(NSString *)needle {
NSInteger n = haystack.length;
NSInteger m = needle.length;
if (m <= 0) {
return 0;
}
NSMutableArray *next = [NSMutableArray array];
for (NSInteger i=0; i<m; i++) {
next[i] = @(0);
}
//求next数组
NSInteger i=1;
NSInteger j = 0;
for (; i<m; i++) {
//不相等的情况
if (j>0 && [needle characterAtIndex:i] != [needle characterAtIndex:j]) {
j = [next[j-1] integerValue];
}
//相等情况
if ([needle characterAtIndex:i] == [needle characterAtIndex:j]) {
j++;
}
//赋值
next[i] = [NSNumber numberWithInteger:j];
}
j = 0;
for (i=0; i<n; i++) {
if (j > 0 && [haystack characterAtIndex:i] != [needle characterAtIndex:j]) {
j = [next[j-1] integerValue];
}
if ([haystack characterAtIndex:i] == [needle characterAtIndex:j]) {
j++;
}
if (j == m) {
return i-m+1;
}
}
return -1;
}
文章来源:https://blog.csdn.net/zzl819954692/article/details/135364688
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!