문제 설명

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),

문제풀이

어렵다.. 이것도 DP 맞나요..ㅜ

class Solution {
    
    func getPalindromeLength(_ i: Int, _ j: Int, _ string: inout [String]) -> Int {
        
        if j >= string.count { return 0 }
        
        var i = i
        var j = j
        var length: Int = i == j ? -1 : 0
        
        while (i>=0 && j<string.count) {
            if string[i] != string[j] { break }
            length += 2
            i -= 1
            j += 1
        }
        
        return length
    }
    
    func longestPalindrome(_ s: String) -> String {
        var string = s.compactMap { String($0) }
        var maxLength = 0
        var start = -1
        
        for i in 0..<string.count {
            let length = max(getPalindromeLength(i, i, &string), getPalindromeLength(i, i+1, &string))
            if maxLength < length {
                maxLength = length
                start = i - (length - 1) / 2
            }
        }
        
        return string[start..<start+maxLength].reduce("", +)
    }
    
}

참고 : https://leetcode.com/problems/longest-palindromic-substring/