LeetCode 5 - Longest Palindromic Substring

LeetCode 5 - Longest Palindromic Substring

해결방안

1. len < 2 면 이미 팰린드롬이기에 바로 s 반환
2. 팰린드롬 문자열의 길이는 홀수, 짝수 둘 다 모두 가능함
3. 팰린드롬은 확인 방법 = 중앙 값으로부터 l, r 을 설정해 점점 멀어지며 같은 문자열인지 확인
4. 0부터 len 까지 반복문 → i 가 중앙점이 되며 이 중앙점으로 부터 팰린드롬 검사
5. 새로 구한 팰린드롬 최대 길이 인덱스를 저장

class Solution {
    var left = 0
    var maxLen = 0
    fun longestPalindrome(s: String): String {
        val len = s.length
        if (len < 2) return s

        for(i in 0 until len ) {
            extendPalindrome(s, i, i)
            extendPalindrome(s, i, i + 1)
        }
        return s.substring(left, left + maxLen)
    }

    private fun extendPalindrome(s: String, j: Int, k: Int) {
        var l = j
        var r = k
        while(l >= 0 && r < s.length && s[l] == s[r]) {
            l--
            r++
        }
        if(maxLen < r - l -1) {
            left = l + 1
            maxLen = r - l - 1

            println("r = $r   l = $l   r - l - 1 = ${r - l - 1}   left = $left    maxLen = ${r - l - 1}")
        }
    }
}

fun main() {
    val c = Solution()
    println(c.longestPalindrome("babad"))
}