LeetCode 28.找出字符串中第一个匹配项的下标

找出字符串中第一个匹配项的下标

给你两个字符串 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;
}