[LeetCode] 5번 - Longest Palindromic Substring [Swift]

문제 링크

Longest Palindromic Substring - LeetCode

문제

Given a string s, return the longest palindromic substring in s.

 

Example 1:

Input: s = "babad"

Output: "bab"

Note: "aba" is also a valid answer.

 

Example 2:

Input: s = "cbbd"

Output: "bb"

 

Example 3:

Input: s = "a"

Output: "a"

 

Example 4:

Input: s = "ac"

Output: "a"

 

Constraints:

• 1 <= s.length <= 1000
• s consist of only digits and English letters (lower-case and/or upper-case),

문제 풀이

이 문제는 주어진 문자열에서 가장 긴 Palindrome을 찾는 문제입니다.

Palindrome은 회문이라고 하는데, 한국어로 보면 기러기, 오디오와 같이 글자를 뒤집어도 같은 글자가 나오는 글자를 말합니다.

주어진 문자열에서 가장 긴 회문을 찾는게 이 문제의 목표입니다.

 

주어진 문자열로 한 번 보면,

"babad"가 주어졌습니다.

가장 긴 회문은 "bab", "aba"가 될 수 있겠네요!

 

어쨌든 이렇게 가장 긴 회문을 구할 수 있는데 어떻게 구해야할지...를 고민하다가! 발견한 규칙은 아래와 같습니다.

 

1. 일단 회문이라고 한다면 첫 글자와 마지막 글자가 같아야한다는 조건이 반드시 필요합니다.
2. 첫 글자와 마지막 글자가 같은데 두 글자 사이에 글자가 하나이하로 있다면 해당 문자열은 회문입니다.
3. 첫 글자와 마지막 글자 사이에 두 개 이상의 글자가 있다면 사이에 있는 문자열이 회문인지에 여부에 따라 회문이 될 수 있습니다.

이를 위해서는 특정 범위의 글자가 회문인지 기록해두는 2차원 배열을 하나 만들어서 해당 배열에 계속 정보를 업데이트 해주면 됩니다.

 

모든 글자에 대해 위의 과정을 해줬다면 문제의 답이 가장 긴 회문을 찾아달라고 했기 때문에 회문이 가능한 글자중에서 가장 긴 녀석을 반환해주시면 됩니다.

 

가장 긴 녀석은 특정 범위의 글자가 회문인지 기록해두는 2차원 배열에서 행번호 - 열번호의 절대값이 가장 큰 값에 해당하는 글자가 되는데요, 전 이걸 회문인지 확인하는 곳에서 바로 처리했습니다.

소스 코드

import Foundation
class Solution {
    func longestPalindrome(_ s: String) -> String {
        if s.count < 2 {
            return s
        }
        let input = s.map({String($0)})
        var left: Int = 0
        var right: Int = 0
        
        // [i][j]가 true라면 s의 i번째 글자부터 j번째 글자까지는 회문이다! 라는 뜻입니다.
        var isPalindrome = [[Bool]](repeating: [Bool](repeating: false, count: s.count), count: s.count)
        
        // i == right, j == left
        for i in 0..<s.count {
            for j in 0..<i {
                // 얘들 사이에 존재하는 애가 회문이거나 사이에 존재하는 글자가 한 글자인 경우엔 반드시 회문
                if input[i] == input[j] && (isPalindrome[i-1][j+1] || i - j <= 2)  {
                    isPalindrome[i][j] = true
                    // 만약 이번에 만든 회문이 기존의 회문 길이보다 작다면 초기화
                    if i - j > right - left {
                        left = j
                        right = i
                    }
                }
            }
        }

        return Array(input[left...right]).joined()
    }
}