Swift 实现strStr() - LeetCode

韦弦zhy

发布于 2018-09-11 11:59:47

8280

发布于 2018-09-11 11:59:47

文章被收录于专栏：韦弦的偶尔分享

LeetCode.jpg

题目：实现strStr()

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

说明：

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

对于本题而言，当 needle 是空字符串时我们应当返回 0 。这与C语言的 strstr() 以及 Java的 indexOf()(https://docs.oracle.com/javase/7/docs/api/java/lang/String.html#indexOf(java.lang.String%29) 定义相符。

案例1：

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

案例2:

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

方案一：第一个闪进我脑瓜子里面的就是切割字符串啦、、、、四行代码解决问题、、、

代码一：

func strStr(_ haystack: String, _ needle: String) -> Int {
    
    if needle.isEmpty {
        return 0
    }
    
    let array = haystack.components(separatedBy: needle)
    
    if array.first!.count == haystack.count {
        return -1
    }
    
    return array.first!.count
}

提交记录：

image.png

很打脸有木有。。。为什么要运行这么久？？？？？？？？哎，切割字符串底层实现我就不纠结了，但是想一想切割字符串的前提是不是要找到该字符串、、、既然找到了，这题就解决了、、、还去切什么切？

所以：

方案二：直接找字符串位置

1、needle判空

2、取两个字符串的长度，hLength,nLength

3、判断前者长度不小于后者

4、取长度的差，循环遍历，

5、在haystack中取nLength长度的字符，判断是否等于needle,有则返回

Swift中取范围内字符子串参考：Swift4 获取String子字符串

代码二：

func strStr(_ haystack: String, _ needle: String) -> Int {
    
    if needle.isEmpty {
        return 0
    }
    let hLength = haystack.count
    let nLength = needle.count
    if hLength < nLength {
        return -1
    }
    
    let threshold = hLength - nLength
    
    for i in 0...threshold {
        if (haystack[haystack.index(haystack.startIndex, offsetBy: i)..<haystack.index(haystack.startIndex, offsetBy: i + nLength)] == needle) {
            return i
        }
    }
    
    return -1
}