[LeetCode] 5. Longest Palindromic Substring / Swift

[문제 보기]

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

 

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

Longest Palindromic Substring - LeetCode

 

---

 

시간초과가 계속떠서 굉장히 시행착오를 많이했다.

구현한 방법은 O(n^2)의 방법이지만

Manacher 알고리즘을 쓰면 O(n)에 구할 수 있는 방법도 있다고 함. (단 짝수개의 경우를 구할 수 없어서 이 경우는 더미 문자를 끼워넣어서 구하거나 해야한다고 함)

https://en.wikipedia.org/wiki/Longest_palindromic_substring#Manacher's_algorithm

Longest palindromic substring - Wikipedia

 

class Solution {
    func expandAroundCenter(_ left: Int, _ right: Int) -> Int {
        var L = left, R = right
        while L >= 0 && R < str.count && str[L] == str[R] {
            L -= 1
            R += 1
        }
        return R - L - 1
    }
    
    var str = [String]()
    
    func longestPalindrome(_ s: String) -> String {
        if s.isEmpty || s.count < 1 { return "" }
        str = s.map{String($0)}
        var start = 0, end = 0
        for i in (0..<str.count) {
            var len1 = expandAroundCenter(i, i)
            var len2 = expandAroundCenter(i, i+1)
            var len = max(len1, len2)
            if len > end - start {
                start = i - (len - 1) / 2
                end = i + len / 2
            }
        }
        
        let range = s.index(s.startIndex, offsetBy: start)...s.index(s.startIndex, offsetBy: end)
        return String(s[range])
    }
}