[Swift]LeetCode28.实现strStr()|ImplementstrStr()

OStack程序员社区-中国程序员成长平台 › 门户 › 编程› 移动开发›Swift 教程

原作者: [db:作者] 来自: [db:来源] 收藏邀请

★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
➤微信公众号：山青咏芝（shanqingyongzhi）
➤博客园地址：山青咏芝（https://www.cnblogs.com/strengthen/）
➤GitHub地址：https://github.com/strengthen/LeetCode
➤原文地址：https://www.cnblogs.com/strengthen/p/9697924.html
➤如果链接不是山青咏芝的博客园地址，则可能是爬取作者的文章。
➤原文已修改更新！强烈建议点击原文地址阅读！支持作者！支持原创！
★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★

热烈欢迎，请直接点击！！！

进入博主App Store主页，下载使用各个作品！！！

注：博主将坚持每月上线一个新app！！！

Implement strStr().

Return the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack.

Example 1:

Input: haystack = "hello", needle = "ll"
Output: 2

Example 2:

Input: haystack = "aaaaa", needle = "bba"
Output: -1

Clarification:

What should we return when needle is an empty string? This is a great question to ask during an interview.

For the purpose of this problem, we will return 0 when needle is an empty string. This is consistent to C's strstr() and Java's indexOf().

实现 strStr() 函数。

给定一个 haystack 字符串和一个 needle 字符串，在 haystack 字符串中找出 needle 字符串出现的第一个位置 (从0开始)。如果不存在，则返回 -1。

示例 1:

输入: haystack = "hello", needle = "ll"
输出: 2

示例 2:

输入: haystack = "aaaaa", needle = "bba"
输出: -1

说明:

当 needle 是空字符串时，我们应当返回什么值呢？这是一个在面试中很好的问题。

对于本题而言，当 needle 是空字符串时我们应当返回 0 。这与C语言的 strstr() 以及 Java的 indexOf() 定义相符。

12ms

 1 class Solution {
 2     func strStr(_ haystack: String, _ needle: String) -> Int {
 3         let count1 = haystack.count
 4         let count2 = needle.count
 5         if count2 == 0 {
 6             return 0
 7         }
 8         
 9         if count1 < count2 {
10             return -1
11         }
12         
13         var haystackChars = haystack.cString(using: .utf8)!
14         var needleChars = needle.cString(using: .utf8)!
15         var i = 0
16         var j = 0
17         
18         let maxi = count1 - count2
19         let maxj = count2 - 1
20         
21         while i <= maxi && j <= maxj {
22             var m = i
23             while m <= count1 - 1 && j <= maxj {
24                 let mv = haystackChars[m]
25                 let jv = needleChars[j]
26                 if mv == jv {
27                     m += 1
28                     j += 1
29                     continue
30                 }
31                 j = 0
32                 i += 1
33                 break
34             }
35         }
36         j = j - 1
37         if j == maxj{
38             return i
39         }
40         
41         return -1
42     }
43 }

16ms

 1 class Solution {
 2 
 3 func strStr(_ haystack: String, _ needle: String) -> Int {
 4     guard needle.count != 0 && !haystack.hasPrefix(needle) else{
 5         return 0
 6     }
 7     guard haystack.count != needle.count else {
 8         return -1
 9     }
10     guard haystack.contains(needle) else {
11         return -1
12     }
13    
14     var stop = false
15     var low = 0
16     var high = haystack.count
17     
18     while !stop {
19         let start = haystack.index(haystack.startIndex, offsetBy: low)
20         let end = haystack.index(haystack.endIndex, offsetBy: high-haystack.count)
21         let range = Range<String.Index>(uncheckedBounds: (lower: start, upper: end))
22         
23         let str = String(haystack[range])
24   
25         if str.count <= needle.count*3 {
26             if str.hasPrefix(needle) {
27                 stop = true
28                 return low
29             }else {
30                 low += 1
31             }
32         }else {
33             let middle = str.count/2
34             let prefixStr = str.prefix(middle + needle.count)
35             if prefixStr.contains(needle) {
36                 if str.hasPrefix(needle) {
37                     stop = true
38                     return low
39                 }
40                 high -= middle
41                 high += needle.count
42             }else {
43                 low += middle
44                 low -= needle.count
45             }
46         }
47     }
48   }
49 }

20ms

 1 class Solution {
 2     func strStr(_ haystack: String, _ needle: String) -> Int {
 3         guard !needle.isEmpty else {
 4             return 0
 5         }
 6         let sCount = haystack.count, pCount = needle.count
 7         guard sCount >= pCount else {
 8             return -1
 9         }
10         let s = Array(haystack), p = Array(needle)
11         var i = 0, j = 0
12         while i < s.count && j < p.count {
13             if s[i] == p[j] {
14                 i += 1
15                 j += 1
16             } else {
17                 i = i - j + 1
18                 j = 0
19             }
20         }
21         return j == pCount ? i - j : -1
22     }
23 }

24ms

 1 class Solution {
 2     func strStr(_ haystack: String, _ needle: String) -> Int {
 3         if needle.count == 0 {
 4             return 0
 5         }
 6 
 7         if haystack.count == 0 {
 8             return -1
 9         }
10 
11         var search = haystack[haystack.startIndex..<haystack.endIndex]
12         while search.count > 0 {
13             if let first = search.firstIndex(of: needle.first!), let endindex = search.index(first, offsetBy: needle.count, limitedBy: search.endIndex) {
14                 let match = search[first..<endindex]
15                 if match == needle {
16                     return haystack.distance(from: haystack.startIndex, to: first)
17                 }
18 
19                 if first != search.endIndex {
20                     if let b = search.index(first, offsetBy: 1, limitedBy: search.endIndex) {
21                         search = search[b..<search.endIndex]
22                     }
23                 }
24             } else {
25                 break
26             }
27         }
28 
29         return -1
30     }
31 }

28ms

 1 class Solution {
 2     func strStr(_ haystack: String, _ needle: String) -> Int {
 3         let sCount = haystack.count, pCount = needle.count
 4         guard pCount > 0 && sCount >= pCount else {
 5             return pCount == 0 ? 0 : -1
 6         }
 7         let p = Array(needle)
 8         //为了提高效率，用空间换时间，初始化一个字典记录p中每个字符最后出现的位置
 9         var charDictionary = [Character: Int]()
10         for index in stride(from: pCount - 1, through: 0, by: -1) {
11             let char = p[index]
12             if charDictionary[char] == nil {
13                 charDictionary[char] = index
14             }
15         }
16         let s = Array(haystack)
17         var i = 0, j = 0
18         while i < sCount && j < pCount {
19             if s[i] == p[j] {
20                 i += 1
21                 j += 1
22             } else {
23                 let nextSCharIndex = i + (pCount - 1 - j) + 1
24                 if nextSCharIndex < sCount {
25                     let nextSChar = s[nextSCharIndex]
26                     if let index = charDictionary[nextSChar] {
27                         i = i - j + pCount - 1 - index + 1
28                     } else {
29                         i = i - j + pCount + 1
30                     }
31                     j = 0
32                 } else {
33                     break
34                 }
35             }
36         }
37         return j == pCount ? i - j : -1
38     }
39 }

32ms

 1 class Solution {
 2     func strStr(_ haystack: String, _ needle: String) -> Int {
 3         guard !needle.isEmpty else {
 4             return 0
 5         }
 6         let sCount = haystack.count, pCount = needle.count
 7         guard sCount >= pCount else {
 8             return -1
 9         }
10         let s = Array(haystack), p = Array(needle)
11         var next = Array(repeating: -1, count: pCount)
12         var k = -1, j = 0
13         while j < pCount - 1 {
14             if k == -1 || p[j] == p[k] {
15                 j += 1
16                 k += 1
17                 if p[j] != p[k] {
18                     next[j] = k
19                 } else {
20                     next[j] = next[k]
21                 }
22             } else {
23                 k = next[k]
24             }
25         }
26         var i = 0
27         j = 0
28         while i < s.count && j < p.count {
29             if j == -1 || s[i] == p[j] {
30                 i += 1
31                 j += 1
32             } else {
33                 j = next[j]
34             }
35         }
36         return j == pCount ? i - j : -1
37     }
38 }

44ms

 1 class Solution {
 2     func strStr(_ haystack: String, _ needle: String) -> Int {   
 3         //当 needle 是空字符串时应当返回 0
 4         if needle.isEmpty{return 0}
 5         //获取字符的长度
 6         let haystackLen = haystack.count
 7         let needleLen = needle.count
 8         //haystack字符串字符长度小于needle字符串，则返回-1
 9         if haystackLen < needleLen{return -1}
10         //needle的第一个字符
11         let firstChar = needle[needle.startIndex]
12         //遍历haystack字符串,讲Int转化为String.Index
13         for i in 0...haystackLen-needleLen
14         {
15             //截取字符串的开始处索引
16             let firstIndex = haystack.index(haystack.startIndex, offsetBy: i)
17             //截取字符串的结束处索引
18             let endIndex = haystack.index(haystack.startIndex, offsetBy: i + needleLen)
19             //截取字符串，注意要用String.Index的方式访问字符串
20             let subStr = haystack[firstIndex..<endIndex]
21             //判断截取的字符串是否等于needle
22             if subStr == needle
23             {
24                 //返回索引
25                 return i
26             }              
27         }
28         //没有匹配，返回-1
29         return -1
30     }
31 }

52ms

 1 class Solution {
 2     func strStr(_ haystack: String, _ needle: String) -> Int {
 3         guard !needle.isEmpty else { return 0 }
 4         guard needle.count <= haystack.count else { return -1 }
 5         for i in 0...(haystack.count-needle.count) {
 6             let substr = String(Array(haystack)[i..<(i+needle.count)])
 7             if substr == needle {
 8                 return i
 9             }
10         }
11         return -1
12     }
13 }