5. Longest Palindromic Substring

Medium

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.
Java
복사

Example 2:

Input: s = "cbbd"
Output: "bb"
Java
복사

Example 3:

Input: s = "a"
Output: "a"
Java
복사

Example 4:

Input: s = "ac"
Output: "a"
Java
복사

Constraints:

•

1 <= s.length <= 1000

•

s consist of only digits and English letters.

My solution

const longestPalindrome = function (s) {
    return s === [...s].reverse().join('')
        ? s
        : longestPalindrome(s.slice(0, -1)).length >= longestPalindrome(s.slice(1)).length
        ? longestPalindrome(s.slice(0, -1))
        : longestPalindrome(s.slice(1));
};
test('TC5', () => {
    expect(longestPalindrome('xaabacxcabaaxcabaax')).toStrictEqual('xaabacxcabaax');
});
JavaScript
복사

⇒ 시간 초과 발생, 반복문을 이용한 이분탐색(투포인터 알고리즘)을 적용해야 함

const longestPalindrome = s => {
    let answer = s[0];
    let lt = 0;
    let rt = s.length - 1;

    while (lt <= rt) {
        const subStr = [...s].slice(lt, rt + 1);
        if (subStr.join('') === subStr.reverse().join('')) {
            answer = answer.length < s.slice(lt, rt + 1).length ? s.slice(lt, rt + 1) : answer;
            ++lt;
            rt = s.length - 1;
        } else --rt;
    }
    return answer;
};
test('TC6', () => {
    expect(
        longestPalindrome(
            'ibvjkmpyzsifuxcabqqpahjdeuzaybqsrsmbfplxycsafogotliyvhxjtkrbzqxlyfwujzhkdafhebvsdhkkdbhlhmaoxmbkqiwiusngkbdhlvxdyvnjrzvxmukvdfobzlmvnbnilnsyrgoygfdzjlymhprcpxsnxpcafctikxxybcusgjwmfklkffehbvlhvxfiddznwumxosomfbgxoruoqrhezgsgidgcfzbtdftjxeahriirqgxbhicoxavquhbkaomrroghdnfkknyigsluqebaqrtcwgmlnvmxoagisdmsokeznjsnwpxygjjptvyjjkbmkxvlivinmpnpxgmmorkasebngirckqcawgevljplkkgextudqaodwqmfljljhrujoerycoojwwgtklypicgkyaboqjfivbeqdlonxeidgxsyzugkntoevwfuxovazcyayvwbcqswzhytlmtmrtwpikgacnpkbwgfmpavzyjoxughwhvlsxsgttbcyrlkaarngeoaldsdtjncivhcfsaohmdhgbwkuemcembmlwbwquxfaiukoqvzmgoeppieztdacvwngbkcxknbytvztodbfnjhbtwpjlzuajnlzfmmujhcggpdcwdquutdiubgcvnxvgspmfumeqrofewynizvynavjzkbpkuxxvkjujectdyfwygnfsukvzflcuxxzvxzravzznpxttduajhbsyiywpqunnarabcroljwcbdydagachbobkcvudkoddldaucwruobfylfhyvjuynjrosxczgjwudpxaqwnboxgxybnngxxhibesiaxkicinikzzmonftqkcudlzfzutplbycejmkpxcygsafzkgudy'
        )
    ).toStrictEqual('fklkf');
});
JavaScript
복사

⇒ 시간 초과 발생,

sub2n.github.io

https://sub2n.github.io/2019/04/22/LeetCode-5-Longest-Palindromic-Substring/

참고해서 풀이

O(n) : 입력 데이터의 크기와 배열의 길이에 비례한 시간이 걸리는 알고리즘. (선형)

성능 느림

DP사용

https://myeongcs.tistory.com/102

소스코드

/**
 * @param {string} s
 * @return {string}
 */
const longestPalindrome = s => {
    const n = s.length;
    let answer = s[0];
    const dp = [...Array(n)].map(() => [...Array(n)].fill(false));

    for (let i = 0; i < s.length; ++i) {
        dp[i][i] = true;
    }
    // & : 2-substring(가장 앞에 위치한 것) 확인
    for (let i = 0; i < s.length - 1; ++i) {
        dp[i][i + 1] = s[i] === s[i + 1];
        if (dp[i][i + 1] && answer.length < 2) answer = s.substring(i, i + 2);
    }

    for (let len = 3; len <= s.length; ++len) {
        // & : 3자리부터 검사, (i + 1) ~ (j - 1)이 palindrome인지 확인
        for (let i = 0, j = i + len - 1; j < s.length; ++i, ++j) {
            dp[i][j] = dp[i + 1][j - 1] && s[i] === s[j];
            if (dp[i][j] && answer.length < len) {
                answer = s.substring(i, i + len);
            }
        }
    }

    return answer;
};

// test('TC1', () => {
//     expect(longestPalindrome('babad')).toStrictEqual('bab');
// });
test('TC2', () => {
    expect(longestPalindrome('cbbd')).toStrictEqual('bb');
});
// test('TC3', () => {
//     expect(longestPalindrome('a')).toStrictEqual('a');
// });
// test('TC4', () => {
//     expect(longestPalindrome('ac')).toStrictEqual('a');
// });
// test('TC5', () => {
//     expect(longestPalindrome('xaabacxcabaaxcabaax')).toStrictEqual('xaabacxcabaax');
// });
// test('TC6', () => {
//     expect(
//         longestPalindrome(
//             'ibvjkmpyzsifuxcabqqpahjdeuzaybqsrsmbfplxycsafogotliyvhxjtkrbzqxlyfwujzhkdafhebvsdhkkdbhlhmaoxmbkqiwiusngkbdhlvxdyvnjrzvxmukvdfobzlmvnbnilnsyrgoygfdzjlymhprcpxsnxpcafctikxxybcusgjwmfklkffehbvlhvxfiddznwumxosomfbgxoruoqrhezgsgidgcfzbtdftjxeahriirqgxbhicoxavquhbkaomrroghdnfkknyigsluqebaqrtcwgmlnvmxoagisdmsokeznjsnwpxygjjptvyjjkbmkxvlivinmpnpxgmmorkasebngirckqcawgevljplkkgextudqaodwqmfljljhrujoerycoojwwgtklypicgkyaboqjfivbeqdlonxeidgxsyzugkntoevwfuxovazcyayvwbcqswzhytlmtmrtwpikgacnpkbwgfmpavzyjoxughwhvlsxsgttbcyrlkaarngeoaldsdtjncivhcfsaohmdhgbwkuemcembmlwbwquxfaiukoqvzmgoeppieztdacvwngbkcxknbytvztodbfnjhbtwpjlzuajnlzfmmujhcggpdcwdquutdiubgcvnxvgspmfumeqrofewynizvynavjzkbpkuxxvkjujectdyfwygnfsukvzflcuxxzvxzravzznpxttduajhbsyiywpqunnarabcroljwcbdydagachbobkcvudkoddldaucwruobfylfhyvjuynjrosxczgjwudpxaqwnboxgxybnngxxhibesiaxkicinikzzmonftqkcudlzfzutplbycejmkpxcygsafzkgudy'
//         )
//     ).toStrictEqual('fklkf');
// });
// test('TC7', () => {
//     expect(
//         longestPalindrome(
//             'civilwartestingwhetherthatnaptionoranynartionsoconceivedandsodedicatedcanlongendureWeareqmetonagreatbattlefiemldoftzhatwarWehavecometodedicpateaportionofthatfieldasafinalrestingplaceforthosewhoheregavetheirlivesthatthatnationmightliveItisaltogetherfangandproperthatweshoulddothisButinalargersensewecannotdedicatewecannotconsecratewecannothallowthisgroundThebravelmenlivinganddeadwhostruggledherehaveconsecrateditfaraboveourpoorponwertoaddordetractTgheworldadswfilllittlenotlenorlongrememberwhatwesayherebutitcanneverforgetwhattheydidhereItisforusthelivingrathertobededicatedheretotheulnfinishedworkwhichtheywhofoughtherehavethusfarsonoblyadvancedItisratherforustobeherededicatedtothegreattdafskremainingbeforeusthatfromthesehonoreddeadwetakeincreaseddevotiontothatcauseforwhichtheygavethelastpfullmeasureofdevotionthatweherehighlyresolvethatthesedeadshallnothavediedinvalethatthisnationunsderGodshallhaveanewbirthoffreedomandthatgovernmentofthepeoplebythepeopleforthepeopleshallnotperishfromtheearth'
//         )
//     ).toStrictEqual('ranynar');
// });
JavaScript
복사