28. 实现strStr()(Swift版)

一、题目

实现 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() 定义相符。

二、解题

遍历haystack，然后逐一匹配needle中的字符，匹配失败迭代haystack下一个字符，知道找到i使得needle能完全匹配，并返回i。
时间复杂度为O(n^2)。(haystack.count * needle.count)

三、代码实现

    class Solution {
        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
            while i <= maxi && j < count2 {
                var m = i
                while m < count1 && j < count2 {
                    if haystackChars[m] == needleChars[j] {
                        m += 1
                        j += 1
                        continue
                    }
                    j = 0
                    i += 1
                    break
                }
            }
            if j == count2{
                return i
            }
            return -1
        }
        
        func strStr1(_ 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)!
            
            for i in 0..<haystack.count {
                if i + needle.count <= haystack.count {
                    let strs = haystackChars[i..<(i+needle.count)]
                    var isSame = true
                    var j = 0
                    for s in strs {
                        if s != needleChars[j] {
                            isSame = false
                            break
                        }
                        j += 1
                    }
                    if isSame {
                        return i
                    }
                }else{
                    return -1
                }
            }
            return -1
        }
    }

Demo地址：github