[ LeetCode] 125 Valid Palindrome

📌 Problem

주어진 문자열이 Palindrome인지 확인하여 Boolean을 반환하면 된다. Palindrome은 다음 순서대로 확인이 가능하다.
Step 1. 문자열에서 알파벳과 숫자를 제외한 모든 문자를 제거한다.
Step 2. 모든 알파벳을 소문자로 변환한다.
Step 3. 문자열을 뒤집어도 동일한 문자 순서를 유지하면 palindrome이다.

📌 Solution

간단하게 생각하면 문자열에서 불필요 문자를 제거하고 소문자 변환을 거친 후 양끝에서부터 문자들을 비교하면 된다. 하지만 그러면 문자 제거와 소문자 변환을 하는 시간이 소요된다. 더 빠르게 처리하기 위해서는 투 포인터를 통해 초기 문자열의 양끝부터 비교하는 것이다. 만약 비교하는 문자가 숫자나 알파벳이 아니면 건너뛴다. 또한 대문자이면 소문자로 변환하여 비교한다. 이렇게 하면 O(N)의 시간 복잡도를 가지고 해결할 수 있다.

📌 Code

class Solution {
    fun isPalindrome(s: String): Boolean {
        var (front, back) = 0 to s.lastIndex
        while (front < back) {
            if (!s[front].isLetterOrDigit()) front++
            else if (!s[back].isLetterOrDigit()) back--
            else if (!s[front].equals(s[back], ignoreCase = true)) return false
            else {
                front++
                back--
            }
        }
        return true
    }
}