[리트코드] 5. Longest Palindromic Substring / Javascript

문제주소 : https://leetcode.com/problems/longest-palindromic-substring/

Longest Palindromic Substring - LeetCode

---

<문제 설명>

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.

 

<풀이법>

▒ 한줄 개념: 팰린드롬 ▒ 

특정 인덱스에서 펠린드롬이 되는 경우는 2가지가 있습니다.

 

1: 짝수 펠린드롬 ex) gg, abba, acbbca 

2: 홀수 펠린드롬 ex) cdc, bcacb 

 

반복문을 통해 string의 각 인덱스에 대해 확인하며, 해당 인덱스의 짝수 펠린드롬의 최대 길이와 홀수 펠린드롬의 최대 길이를 구해 기존 최장 펠린드롬과 비교하여 갱신해주면 됩니다.

 

<코드(Javascript)>

/**
 * @param {string} s
 * @return {string}
 */
var longestPalindrome = function(s) {
    return s.split('').reduce((acc, cur, idx, arr) => {
        let evenOffset = 0;
        let oddOffset = 0;
        while(evenOffset <= idx && idx + 1 + evenOffset < arr.length && 
              arr[idx - evenOffset] === arr[idx + 1 + evenOffset]){
            evenOffset++;
        }
        
        while(oddOffset < idx && idx + 1 + oddOffset < arr.length && 
              arr[idx - 1 - oddOffset] === arr[idx + 1 + oddOffset]){
            oddOffset++;
        }

        const evenLength = evenOffset * 2;
        const oddLength = oddOffset ? oddOffset * 2 + 1 : 1;
        if(acc.length > evenLength && acc.length > oddLength){
            return acc;
        }
        else if(evenLength > oddLength){
            return s.substr(idx - evenOffset + 1, evenLength);
        }else{
            return s.substr(idx - oddOffset, oddLength);
        }
    },'')
};

 

 

더 많은 코드 보기(GitHub) : github.com/dwkim-97/CodingTest