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

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

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