一、题目原型:
给定一个 haystack 字符串和一个 needle 字符串,在 haystack 字符串中找出 needle 字符串出现的第一个位置 (从0开始)。如果不存在,则返回 -1。
二、示例剖析:
输入: haystack = "hello", needle = "ll"
输出: 2
输入: haystack = "aaaaa", needle = "bba"
输出: -1
说明:
当 needle 是空字符串时,我们应当返回什么值呢?这是一个在面试中很好的问题。
对于本题而言,当 needle 是空字符串时我们应当返回 0 。这与C语言的 strstr() 以及 Java的 indexOf() 定义相符。
三、解题思路:
1.方法简单,运用swift语言特性
func strStr(_ haystack: String, _ needle: String) -> Int {
if needle.count == 0 {
return 0
}
let range = haystack.range(of: needle)
return range?.lowerBound.encodedOffset ?? -1
}
2.将字符串变成数组,进行遍历。(借鉴top1的方案,其实也简单,就是看起来代码貌似会比较多)
func strStr(_ haystack: String, _ needle: String) -> Int {
let count1 = haystack.count
let count2 = needle.count
if count2 == 0 {
return 0
}
if count1 < count2 {
return -1
}
var haystackChars = haystack.cString(using: .utf8)!
var needleChars = needle.cString(using: .utf8)!
var i = 0
var j = 0
let maxi = count1 - count2
let maxj = count2 - 1
while i <= maxi && j <= maxj {
var m = i
while m <= count1 - 1 && j <= maxj {
let mv = haystackChars[m]
let jv = needleChars[j]
if mv == jv {
m += 1
j += 1
continue
}
j = 0
i += 1
break
}
}
j = j - 1
if j == maxj{
return i
}
return -1
}
四、小结
1.耗时856
毫秒,超过32.58%
的提交记录,总提交数74
。
2.耗时12
毫秒,超过100%
的提交记录,总提交数74
。
网友评论