Longest Palindromic Substring (Medium)

문제

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

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

Example 2:
Input: s = "cbbd"
Output: "bb"

Constraints:
1 <= s.length <= 1000
s consist of only digits and English letters.

 

---

풀이

팰린드롬.. 파이썬으로 할때도 어려웠는데 JS로 할려니까 풀이부터 코드까지 접근 조차 힘들었다..

마찬가지로  브루트포스 방식으로 접근하면 2중 for문을 이용해서 문자열이 같으면 양끝에서 한칸씩 이동하여

비교해서 찾는 방식을 생각했다..

30분이 지나서 코드는 작성하지 못했다..

 

해결책 : 

중심 확장(Center Expansion) 방법을 이용

: 문자열의 각 문자를 중심으로 팰린드롬을 확장해 나가면서 가장 긴 팰린드롬을 찾는 방식

O(n^2)의 시간 복잡도를 가지지만, 확장을 최적화하여 불필요한 비교를 줄일 수 있다

---

답안

/**
 * @param {string} s
 * @return {string}
 */
var longestPalindrome = function(s) {
    if (s.length === 0) return '';

    let start = 0;
    let end = 0;

    for (let i = 0; i < s.length; i++) {
        // 두 경우에 대해 팰린드롬 확장
        let len1 = expandAroundCenter(s, i, i);     // 홀수 길이 팰린드롬
        let len2 = expandAroundCenter(s, i, i + 1); // 짝수 길이 팰린드롬
        let len = Math.max(len1, len2);

        if (len > end - start) {
            start = i - Math.floor((len - 1) / 2);
            end = i + Math.floor(len / 2);
        }
    }

    return s.substring(start, end + 1);
};

// 중심 확장을 위한 헬퍼 함수
function expandAroundCenter(s, left, right) {
    while (left >= 0 && right < s.length && s[left] === s[right]) {
        left--;
        right++;
    }
    return right - left - 1; // 길이 반환
}