[LeetCode] 5. Longest Palindromic Substring (팰린드롬)

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

Longest Palindromic Substring - LeetCode

 

핵심 아이디어

팰린드롬 문자열이란 문자를 거꾸로 했을때 기존의 문자열과 같은 문자열을 뜻한다.

이 문제를 해결하는 방법은 많으나 여기서 소개하는 방법은 DP를 이용한 방법이다.

여기서 가장 중요한 핵심은 "현재 문자열의 양끝 문자가 같고 내부의 문자열이 펠린드롬이면 그 문자열은 펠린드롬이다."이다.

즉, ababa은 ababa 으로 양끝이 같은데, 내부 문자열인 ababa 가 펠린드롬이기 때문에, 펠린드롬 문자열이라고 판단할 수 있다.

이 점을 이용하여 dp[i][j] 를 문자열 i~j까지 펠린드롬 여부로 정의하여 문자열의 길이가 1,2 인 경우를 전처리해주고,

그 이상 문자열은 현재 문자열의 양끌을 체크하고 해당 문자열의 i+1~j-1까지의 범위가 펠린드롬인지를 판단하고

만약 펠린드롬이면 가장 긴 펠린드롬 문자열을 업데이트하는 방식으로 문제를 해결할 수 있다.

 

/**
 * @param {string} s
 * @return {string}
 */
var longestPalindrome = function (s) {
	let ans = '';
	// dp[a][b] : s의 a~b까지는 펠린드롬인가?
	const dp = Array.from({ length: s.length+1 }, () =>
		Array.from({ length: s.length+1 }, () => false)
	);

	// i부터 i까지는 1자리 아므로 항상 펠린드롬이다.
	for (let i = 0; i < s.length; i++) {
		dp[i][i] = true;
		ans = s[i];
	}

	// i부터 i+1까지는 2자리이므로 2자리가 같은경우 팰린드롬이다.
	for (let i = 0; i < s.length; i++) {
		if (s[i] === s[i + 1]) dp[i][i + 1] = true;
		if (dp[i][i + 1]) ans = s.slice(i, i + 2);
	}

	for (let i = s.length - 1; i >= 0; i--) {
		for (let j = i + 2; j < s.length; j++) {
			// 양끝이 같고, 안쪽의 문자열이 펠린드롬이면 지금 문자열도 펠린드롬!
			dp[i][j] = dp[i + 1][j - 1] && s[i] === s[j];
			if (dp[i][j]) {
				ans = ans.length < (j - i + 1) ? s.slice(i, j + 1) : ans;
			}
		}
	}
	
	return ans;
};