[Algorithm] LeetCode - Longest Palindromic Substring

📠 문제

• Longest Palendromic Substring
• 난이도: Medium
• 문자열 s가 주어질 때, s에서 가장 긴 팰린드롬 부분 문자열을 찾는 문제이다.
• 팰린드롬이란, 앞에서 읽든 뒤에서 읽든 같은 문자열을 말한다.

Input: s = "babad"
Output: "bab"
Explanation: "aba" is also a valid answer.

💡 풀이

결국 팰린드롬은 중심을 기준으로 대칭이 되어야 한다. 팰린드롬의 종류는 두가지인데 aa처럼 짝수로 된 팰린드롬이 있을 수 있고, aba처럼 홀수로 된 팰린드롬이 있을 수 있다.

 

따라서 중심으로부터 펼쳐(?)나가는 식으로 코드를 작성하면 O(n^2)의 시간복잡도로 구할 수 있다.

func longestPalindrome(_ s: String) -> String {
    guard !s.isEmpty else { return "" }
    
    let chars = Array(s)
    var start = 0, end = 0

    for i in chars.indices {
        let oddLength = palindromeLength(from: i, to: i, in: chars)
        let evenLength = palindromeLength(from: i, to: i + 1, in: chars)
        let maxLength = max(oddLength, evenLength)

        if maxLength > end - start {
            start = i - (maxLength - 1) / 2
            end = i + maxLength / 2
        }
    }

    return String(chars[start...end])
}

private func palindromeLength(from left: Int, to right: Int, in chars: [Character]) -> Int {
    var l = left, r = right
    
    while l >= 0 && r < chars.count && chars[l] == chars[r] {
        l -= 1
        r += 1
    }
    
    return r - l - 1
}