[LeetCode] 5. Longest Palindromic Substring

https://leetcode.com/

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.

 

Code :

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);
        }
    }, '');
};

 

Solutions Code :

var check = function(s, i, j) {
    // i가 j보다 작은 동안 계속 반복
    while (i < j) {
        // 문자열의 i번째와 j번째 문자를 비교하여 다르면 false 반환
        if (s[i] !== s[j]) {
            return false;
        }
        // i를 증가, j를 감소하여 다음 문자 비교
        i++;
        j--;
    }
    // 모든 비교에서 다르지 않았으면 true 반환 (팰린드롬)
    return true;
}

var longestPalindrome = function(s) {
    const n = s.length; // 문자열의 길이
    let starting_index = 0; // 팰린드롬 부분 문자열의 시작 인덱스
    let max_len = 0; // 가장 긴 팰린드롬 부분 문자열의 길이
    // 이중 반복문을 통해 모든 부분 문자열에 대해 팰린드롬 여부를 확인
    for (let i = 0; i < n; i++) {
        for (let j = i; j < n; j++) {
            // check 함수를 사용하여 부분 문자열이 팰린드롬인지 확인
            if (check(s, i, j)) {
                // 현재 부분 문자열이 이전까지 찾은 가장 긴 팰린드롬보다 길면 업데이트
                if (j - i + 1 > max_len) {
                    max_len = j - i + 1;
                    starting_index = i;
                }
            }
        }
    }
    // 가장 긴 팰린드롬 부분 문자열을 추출하여 반환
    return s.substring(starting_index, starting_index + max_len);
}

 

출처 : https://leetcode.com/problemset/all/

Problems - LeetCode