LeetCode 5 - Longest Palindromic Substring (Medium)

문제

LeetCode - 5번

풀이 과정

가장 긴 팰린드롬을 구하는 문제입니다.

만약 dp(i, j) = i에서 j까지의 가장 긴 팰린드롬의 길이 라고 정의한다면 다음과 같은 점화식을 세울 수 있습니다.

dp(i, j) = if dp[i] == dp[j] & dp(i+1, j-1) is palindrome, dp(i+1, j-1) + 2 else 0

기저 사례로 각 문자는 길이가 1인 팰린드롬이라는 것에 유의하여 구현하였습니다.

코드

/**
 * @param {string} s
 * @return {string}
 */
var longestPalindrome = function (s) {
  let answer = "";
  const dp = new Array(s.length)
    .fill(null)
    .map((x) => new Array(s.length).fill(-1));

  for (let i = 0; i < s.length; i++) {
    dp[i][i] = 1;
    answer = s[i];
  }

  for (let len = 2; len <= s.length; len++) {
    for (let start = 0; start <= s.length - len; start++) {
      let end = start + len - 1;

      if (s[start] === s[end]) {
        if (start + 1 === end) dp[start][end] = 2;
        else if (dp[start + 1][end - 1]) {
          dp[start][end] = dp[start + 1][end - 1] + 2;
        } else {
          dp[start][end] = 0;
        }
      } else {
        dp[start][end] = 0;
      }

      if (answer.length < dp[start][end]) answer = s.slice(start, end + 1);
    }
  }

  return answer;
};