[LeetCode] 125. Valid Palindrome (해석, Kotlin 풀이)

문제

https://leetcode.com/problems/valid-palindrome/description/

Palindrome 문구는 주어진 문자열에서 모든 대문자를 소문자로 바꾼 후, 영숫자가 아닌 문자들을 지웠을 때, 앞뒤로 똑같이 읽힌다. Alphanumeric(영숫자)는 문자와 숫자를 포함한다.

 

풀이

1. 코틀린 확장함수를 맘껏 활용한 풀이

fun isPalindrome(s: String): Boolean = s.lowercase().filter {
   it.isLetterOrDigit()
}.let {
    it == it.reversed()
}

단 두줄로 문제를 풀 수 있었다.

다만 leetcode 코틀린 버전이 낮아서인지 Deprecated된 함수를 사용하여야 함! (toLowerCase)

시간 복잡도: O(n), 공간 복잡도: O(n)

 

2. 투포인터를 활용한 풀이

fun isPalindromeTwoPointer(s: String): Boolean {
    var left: Int = 0
    var right: Int = s.length - 1

    while(left < right) {
        while(!s[left].isLetterOrDigit() && left < right) left ++
        while(!s[right].isLetterOrDigit() && right > left) right --

        if(s[left].lowercase() != s[right].lowercase()) return false

        left ++
        right --
    }

    return true
}

시간 복잡도: O(n), 공간 복잡도: O(1)

https://github.com/jeongum/algorithm/blob/master/LT_125_ValidPalindrome.kt