LeetCode 28. Implement strStr()

题目

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  

思路

最Naive的思路先,把haystack里的char一个个的iterate, 然后haystack里的相应长度的substring和needle对比,如果相同则可以。 结果看来这个naive的方式也是可以过OJ的。 另外的解法是KMP算法, 这个在另外的一个帖子里po出.

Swift 题解

func strStr(_ haystack: String, _ needle: String) -> Int {  
        if needle.isEmpty {
            return 0
        }

        if needle.count > haystack.count {
            return -1
        }

        if haystack.count == needle.count {
            return haystack == needle ? 0 : -1
        }

        let max = haystack.count - needle.count
        for i in 0...max {
            let startIndex = haystack.index(haystack.startIndex, offsetBy: i)
            let endIndex = haystack.index(startIndex, offsetBy: needle.count)
            let sub = String(haystack[startIndex..<endIndex])
            if sub == needle {
                return i
            }
        }

        return -1
    }

chenbo

编程爱好者

Singapore