[LeetCode] 5. Longest Palindromic Substring (JS)

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

Longest Palindromic Substring - LeetCode

핵심 아이디어

• 모든 문자에 대해 two pointer를 확장해 가며 s[left] === s[right] 를 비교한다
• substring 길이가 홀수인 경우, 짝수인 경우 case로 나눠서 두 번 구한다

 

복잡도

• 시간 복잡도: O(n^2)
  
  • string 모든 문자 순회 N * two pointer 비교 N

설명

"가장 긴 팰린드롬 부분 문자열을 출력하라"

 

팰린드롬: 뒤집어도 같은 문자열 => two pointer 로 s[left] === s[right] 를 이용한다 라는 발상으로 푸는 문제이다. 설명이 빈약해서 당황했었는데 그냥 그걸 n번 반복해서 O(n^2)짜리 문제였다.

substring이 홀수일수도, 짝수일수도 있다는 것에 주의해야 한다. 이 문제에서는 같은 로직을 두 번 돌려서 해결했다.

조건을 만족하는 경우 left, right가 한번 더 움직이고, while문이 끝났을 때는 조건이 맞지 않는 상태라는 점도 주의해야 한다. 따라서 substring을 할 때는 left, right의 이전값을 기준으로 잘라야 한다.

 

코드 (Javascript)

/**
 * @param {string} s
 * @return {string}
 */

var longestPalindrome = function(s) {
    /**
     * get palindrome substirng with two pointers
     */
    const getPalindromeSubstring = (left, right) => {
        while( (left >= 0 && right < s.length) && (s[left] === s[right]) ) {
            left -= 1;
            right += 1;
        }
        
        return s.substring(left + 1, right);
    }
    
    let longest = "";
    
    for(let i = 0; i < s.length; i++) {
        const oddSubstring = getPalindromeSubstring(i,i);
        const evenSubstring = getPalindromeSubstring(i,i+1);
        
        longest = [longest, oddSubstring, evenSubstring].reduce((prev, str) => str.length > prev.length ? str : prev);
    }
    
    return longest;
};

 

유튜브 NeetCode 해설 영상