Leetcode - 가장 긴 Palindromic 하위 문자열(JavaScript 포함)

오늘은 Longest Palindromic Substring을 푸는 방법을 보여드리겠습니다.

문제는 다음과 같습니다.


지난 블로그에서 문자열이 회문인지 여부를 확인하는 방법에 대해 이야기했습니다. 회문은 앞으로 쓰는 것과 뒤로 쓰는 것이 같은 문자열입니다.

그러나 이 문제는 문자열이 회문인지 알아내야 할 뿐만 아니라 가장 긴 회문 하위 문자열도 찾아야 한다는 점에서 약간 다릅니다.

솔루션에 들어가기 전에 단일 문자가 회문으로 간주된다는 점에 유의하고 싶습니다. 예를 들어, 문자 'a'는 앞으로 쓰는 것과 뒤로 쓰는 것이 같기 때문에 회문으로 간주됩니다.

우리는 모든 회문에 중심이 있다는 것을 압니다. 길이가 홀수이면 회문의 중심이 문자입니다. 그러나 길이가 짝수이면 회문의 중심은 두 글자 사이에 있습니다.



입력 문자열을 반복하고 주어진 각 지점을 회문의 중심이 될 수 있는 것처럼 처리할 수 있습니다. 중심은 주어진 문자에 있거나 주어진 문자와 이전 문자 사이에 있을 수 있습니다. 우리가 회문의 한가운데에 있을 때, 우리는 그것을 확장하고 그 옆에 있는 두 글자를 보고 그들이 서로 같은지 볼 수 있습니다. 그리고 그에 따라 현재 가장 긴 회문을 업데이트합니다.

실제로 회문을 저장할 필요는 없습니다. 회문의 시작 문자 인덱스와 마지막 문자 인덱스를 저장할 수 있습니다.

우리는 본질적으로 잠재적 회문의 중심을 계속 확인하고 그것으로부터 확장합니다. 그리고 그것은 결국 O(n^2)에서 실행될 것입니다.

var longestPalindrome = function(s) {
    let currentLongest = [0, 1];

    for (let i=1; i< s.length; i++){
        const odd = expandAroundCenter(s, i-1, i+1); // treating the given letter as a center and checking its surrounding letters 
        const even = expandAroundCenter(s, i-1, i); // checking if the  center is between the given letter and the previous letter
        const longest = odd[1] - odd[0] > even[1] - even[0] ? odd : even; // choosing the longest palindrome between odd and even
        currentLongest = currentLongest[1] - currentLongest[0] > longest [1] - longest[0] ?  currentLongest : longest // comparing the longest to the current longest palindrome and updating current longest accordingly
    } 
    return s.slice(currentLongest[0], currentLongest[1]);
};

function expandAroundCenter(s, leftIdx, rightIdx){
    while (leftIdx >= 0 && rightIdx < s.length){
        if(s[leftIdx] !== s[rightIdx]) break;
        leftIdx--;
        rightIdx++;
    }
    return[leftIdx + 1, rightIdx] 
}