[Swift] 효율적으로 문자열 index 접근하기

LeetCode에서 Implement strStr()라는 문제를 풀면서 나름 재밌는 사실을 알게 되어 적는다.

Swift는 문자열 처리가 살짝 귀찮은 편이라 PS시엔 String을 Array로 한 번 감싸 subscript로 접근하는 편이었다. 이 문제도 당연히 그렇게 접근했는데 엣지케이스로 무지막지하게 긴 문자열이 나와 계속해서 시간초과가 났다.

이걸 어떻게 해결해야 하나.. 싶어 생각해보다가 문득 Array로 String을 감싸는 것 자체가 사실 좋은 퍼포먼스를 보이긴 힘들 것이라는 생각이 들어 가장 정석적인 방법인 String.index로 접근해보았다.

class Solution {
    func strStr(_ haystack: String, _ needle: String) -> Int {
        if needle.isEmpty {
            return 0
        }
        
        var start = 0
        var end = needle.count - 1
        
        while end < haystack.count {
            let startIndex = haystack.index(haystack.startIndex, offsetBy: start)
            let endIndex = haystack.index(haystack.startIndex, offsetBy: end)
            let subStr = String(haystack[startIndex...endIndex])
            
            if subStr == needle {
                return start
            }
            
            start += 1
            end += 1
        }
        
        return -1
    }
}

이런 식으로 접근을 했는데, 여전히 해당 케이스에서 시간초과가 발생했다. 계속 찾아본 결과 해답은 바로..

class Solution {
    func strStr(_ haystack: String, _ needle: String) -> Int {
        if needle.isEmpty { return 0 }
        if needle.count > haystack.count { return -1 }
        
        var startIndex = haystack.index(haystack.startIndex, offsetBy: 0)
        var endIndex = haystack.index(haystack.startIndex, offsetBy: needle.count - 1)
        var index = 0
        
        while endIndex < haystack.endIndex {
            
            let subStr = haystack[startIndex...endIndex]
            
            if subStr == needle {
                return index
            }
            
            startIndex = haystack.index(after: startIndex)
            endIndex = haystack.index(after: endIndex)
            index += 1
        }
        
        return -1
    }
}

와 같이 string.index(after:)를 사용하는 것.
아마 String.index를 매번 생성하는 비용이 꽤나 드는 것 같아 보인다. 물론 어디까지나 몇 만 루프 정도 돌려야 유의미한 차이가 발생하는 정도이긴 하지만, 알고 있어서 나쁠건 없을 것 같다.

• 추가로 String을 가지고 놀 때 subString 등을 하는 것보단, ArraySlice로 변환해서 index 형태로 접근하는 것이 훨씬 빠르다고 한다. https://stackoverflow.com/questions/40371929/slow-swift-string-performance