[LeetCode/Kotlin]Medium - 5. Longest Palindromic Substring

문제 url: https://leetcode.com/problems/longest-palindromic-substring/

 

문제 해석

s라는 문자열을 입력받을 때, 해당 문자열 내에서 앞뒤로 봐도 똑같은 글자들 중 가장 긴 글자를 찾아내면 된다.

---

풀이 방법

풀이 접근 과정

기존에 프로그래머스 Level3 문제에서 가장 긴 팰린드롬 문제를 풀었던 적이 있다.

그 풀이와 유사하게 풀었다.

최종 소스코드

class Solution {
    fun longestPalindrome(s: String): String {
        var cnt = 0
        var answerIdx = Pair(0,0)

        fun palindrom(startIndex: Int, endIndex: Int) {
            val size = endIndex - startIndex + 1
            val midIndex: Int = size / 2
            var isCorrect = true

            for (index in 0 until midIndex) {
                if (s[index+startIndex] != s[endIndex-index]) {
                    isCorrect = false
                    break
                }
            }

            if (isCorrect) {
                cnt = size
                answerIdx = Pair(startIndex, endIndex)
            }

            if (startIndex <= endIndex-1 && size-1 > cnt) palindrom(startIndex, endIndex-1)
        }

        for (i in 0 .. s.length-2) {
            if (i <= s.length-1 && s.length-1 - i + 1 > cnt) palindrom(i, s.length-1)
        }

        return s.substring(answerIdx.first, answerIdx.second+1)
    }
}

문자를 모두 하나하나 비교하는 방법을 사용하였다.

시작 인덱스부터 특정 길이까지 문자열을 자르고, 갈린 문자열 길이의 가운데 인덱스를 기준으로 대칭되는 문자를 비교한다.

대칭되는 문자 모두가 일치하면 answer에 해당 값의 인덱스를 저장한다.

마지막으로 완성된 인덱스를 기준으로 substring하여 리턴시킨다.

---

비슷한 문제: https://school.programmers.co.kr/learn/courses/30/lessons/12904

프로그래머스