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
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。