Fork me on GitHub

Implement strStr()

题目介绍

LeetCode 28. Implement strStr(),实现 strStr() 函数,返回子串在字符串中出现的起始位置,未包含则返回 -1。

解题思路

一开始我用了 Swift 本身语言的特性,如果包含返回 range,取 range 的起始位置即可。

1
2
3
4
5
6
7
8
9
10
11
class Solution1 {
func strStr(_ haystack: String, _ needle: String) -> Int {
guard !needle.isEmpty else {
return 0
}
guard let range = haystack.range(of: needle) else {
return -1
}
return range.lowerBound.encodedOffset
}
}

注意:需要判断子字符串是否为空,是则返回 0;否则会报错如下:

后来想想这个方法确实投机取巧用了语言的特性,所以还是用算法解决问题,two pointer 的算法思路。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
class Solution {
func strStr(_ haystack: String, _ needle: String) -> Int {
if needle.isEmpty {
return 0
}
if needle.count > haystack.count {
return -1
}
let haystackChar = Array(haystack)
let needleChar = Array(needle)
var i = 0
var j = 0
while i < haystackChar.count {
j = 0
if haystackChar.count - i < needleChar.count {
return -1
}
for index in 0..<needleChar.count {
if haystackChar[i + index] == needleChar[index] {
j += 1
continue
} else {
break
}
}
if j == needleChar.count {
return i
} else {
i += 1
}
}
return -1
}
}

版权声明



Ivan’s Blog by Ivan Ye is licensed under a Creative Commons BY-NC-ND 4.0 International License.
叶帆创作并维护的叶帆的博客博客采用创作共用保留署名-非商业-禁止演绎4.0国际许可证

本文首发于Ivan’s Blog | 叶帆的博客博客( http://yeziahehe.com ),版权所有,侵权必究。

本文链接:http://yeziahehe.com/2017/11/18/ImplementstrStr/