Leetcode: Valid Palindrome, 회문 판별

문제설명

Given a string, determine if it is a palindrome, considering only alphanumeric characters and ignoring cases.

Note: For the purpose of this problem, we define empty string as valid palindrome.

풀이방법

문제 조건은 알파벳 또는 숫자만 회문으로 판별한다고 하였으므로, 문자열 배열에 이에 해당하는 것만 추가한다.
그리고, 이 문자열 배열의 양끝을 순회하면서 같은 문자 또는 숫자인지 판별한다.

참고

첫 번째 for 반복문에서, 문자열을 인덱스로 순회하면 타임아웃이 발생한다.
벤치마킹을 위해 CoreFoundation을 임포트하여 확인해보았다.
예제 문자열, "A man, a plan, a canal: Panama"을 이용하면 약 3.8배 정도의 속도 차이가 발생한다.

Character 직접 순회, 0.0017690658569335938 vs 인덱스로 접근시 0.0066699981689453125

import CoreFoundation

func isPalindrome(_ s: String) -> Bool {
    var charArray: [Character] = []
    // eliminate non character
    let startTime = CFAbsoluteTimeGetCurrent()

    for chr in s {
        if chr.isLetter || chr.isNumber {
            charArray.append(contentsOf: chr.lowercased())
        }
    }
    let endTime = CFAbsoluteTimeGetCurrent()

    print(endTime - startTime)
    for i in 0..<charArray.count/2 {
        if charArray[i] != charArray[charArray.count-1-i] {
            return false
        }
    }
    return true
}

print(isPalindrome("A man, a plan, a canal: Panama"))
print(isPalindrome("race a car"))



func isPalindromeSlow(_ s: String) -> Bool {
    var charArray: [Character] = []
    // eliminate non character
    let startTime = CFAbsoluteTimeGetCurrent()
    for index in 0..<s.count {
        let chr = s[s.index(s.startIndex, offsetBy: index)]
        if chr.isLetter || chr.isNumber {
            charArray.append(contentsOf: chr.lowercased())
        }
    }
    let endTime = CFAbsoluteTimeGetCurrent()

    print(endTime - startTime)
    for i in 0..<charArray.count/2 {
        if charArray[i] != charArray[charArray.count-1-i] {
            return false
        }
    }
    return true
}

print(isPalindromeSlow("A man, a plan, a canal: Panama"))
print(isPalindromeSlow("race a car"))