[leetcode]516.Longest Palindromic Subsequence

leetcode 문제 링크

내 깃헙 링크

문제

Given a string s, find the longest palindromic subsequence's length in s.

A subsequence is a sequence that can be derived from another sequence by deleting some or no elements without changing the order of the remaining elements.

• Example 1:
  - Input: s = "bbbab"
  - Output: 4

• Example 2:
  - Input: s = "cbbd"
  - Output: 2

제한사항

1 <= s.length <= 1000
s consists only of lowercase English letters.

풀이1

function solution(s) {
  let max = palindromic(s);
  if (s.length <= 1) return s.length;

  for (let i = 0; i < s.length; i++) {
    const sArray = s.split('');
    const newArray = [...sArray.slice(0, i), ...sArray.slice(i + 1)];
    const temp = palindromic(newArray);
    max = max < temp ? temp : max;
  }
  return max;
}

function palindromic(s) {
  let temp = '';
  let count = 1;
  let max = Number.MIN_SAFE_INTEGER;
  for (let i = 0; i < s.length; i++) {
    if (s[i] == temp) {
      count++;
      max = max < count ? count : max;
    } else {
      count = 1;
      temp = s[i];
    }
  }
  return max;
}

첫번째 풀이는 내가 palindromic의 의미를 계속 반복되는 값이라고만 생각해서 풀게된 풀이였고, submit했을 때 값이 계속 틀려서 문제를 다시 읽고 풀게 되었다.

풀이2

function solution(st) {
  var dp = [];

  function findLPSLengthRecursive(st, startIndex, endIndex) {
    if (startIndex > endIndex) return 0;

    // every sequence with one element is a palindrome of length 1
    if (startIndex === endIndex) return 1;

    dp[startIndex] = dp[startIndex] || [];

    if (typeof dp[startIndex][endIndex] === 'undefined') {
      // case 1: elements at the beginning and the end are the same
      if (st[startIndex] === st[endIndex]) {
        dp[startIndex][endIndex] =
          2 + findLPSLengthRecursive(st, startIndex + 1, endIndex - 1);
      } else {
        // case 2: skip one element either from the beginning or the end
        let c1 = findLPSLengthRecursive(st, startIndex + 1, endIndex);
        let c2 = findLPSLengthRecursive(st, startIndex, endIndex - 1);
        dp[startIndex][endIndex] = Math.max(c1, c2);
      }
    }

    return dp[startIndex][endIndex];
  }

  return findLPSLengthRecursive(st, 0, st.length - 1);
}

추가사항

palindromic subsequence는 dp 문제로 상당히 유명한 문제인 듯했다. 그래서 youtube영상들도 많아서, youtube 영상을 보고 난 뒤 이해할 수 있었다.
참고 유투브 링크