leetcode0005 - Longest Palindromic Substring / Medium / TypeScript

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

Longest Palindromic Substring - LeetCode

• 문자열 탐색 시 0번째 문자부터 마지막 문자까지 순회
• 해당 문자가 palindrome의 중간에 오는 문자가 됨.
• 해당 문자를 기준으로 왼쪽 오른쪽으로 -1, +1씩을 하면서 palindrome이 되는 문자열을 탐색
• 그 중 가장 긴 문자를 찾는다.

Time Complexity O(n^2)

• for 문 안에 while 문으로 탐색

 

const getThePalindrome = (s: string, left: number, right: number): string => {
    while(left >= 0 && right < s.length && s[left] === s[right]) {
        left -= 1;
        right += 1;
    }

    return s.slice(left+1, right);
}


function longestPalindrome(s: string): string {
    let palindrome = '';

    for(let left = 0; left < s.length; left++) {
        const oddPalindrome = getThePalindrome(s, left, left);
        if(oddPalindrome.length > palindrome.length) {
            palindrome = oddPalindrome;
        }

        const evenPalindrome = getThePalindrome(s, left, left+1);
        if(evenPalindrome.length > palindrome.length) {
            palindrome = evenPalindrome;
        }
    }

    return palindrome;
};