5. Longest Palindromic Substring

문제링크: https://leetcode.com/problems/longest-palindromic-substring/

배열에 있는 문자열을 잘라 가장 긴 Palindorme을 찾는 문제다.

Solution

1. Expand with pruning

가운데 값을 지정하고 좌우로 넓혀서 pruning하는 방법이다. 기존의 sliding window 기법은 일정한 범위에서 만족을 하지 않는다면 더 넓혀도 만족하지 않는다는 조건을 이용한 pruning이다. 비슷한 방법으로 palindorme의 경우 다음과 같이 좌우로 넓히는 과정에서 aba > cabac > dcabace처럼 더이상 조건을 만족하지 않는다면 더 좌우로 넓혀도 만족하지 않는다는 점에서 착안해 pruning 할 수 있다.

Algorithm

• s의 인덱스를 통해 중간 값을 지정한다.
• 중간 값의 좌우가 동일한 경우 범위를 점점 넓힌다.
• 배열의 범위를 벗어나거나 다른 값이 발견될 경우 넓히기를 중지한다. (해당 값을 중간으로 가지는 최대 범위)
• 같은 방법으로 연속된 중간값('bb')에도 범위를 넓히고 최대 범위를 구한다.
• 모든 s에서 가능한 중간값에 대해 위의 방법을 반복한다.
• 가장 긴 배열의 인덱스를 저장하고 마지막에 반환한다.

var longestPalindrome = function(s) {
  // brute force
  // get middle and expand
  // get middle 2가지 홀수개, 짝수개
  
  let longest = [0, 0];
  for (let i = 0; i < s.length; i++) {
    // 1. 그냥 원소 하나로 (abcba 홀수개)
    let start = i, end = i;
    while (start > 0 && end < s.length - 1) {
      if (s[start - 1] === s[end + 1]) {
        start--;
        end++;
      } else {
        break;
      }
    }
    if (longest[1] - longest[0] < end - start) {
      longest = [start, end];
    }
    
    // 2. 연속된 원소 (abccba 짝수개)
    if (i !== 0 && s[i - 1] === s[i]) {
      start = i - 1;
      end = i;
      while (start > 0 && end < s.length - 1) {
        if (s[start - 1] === s[end + 1]) {
          start--;
          end++;
        } else {
          break;
        }
      }
      if (longest[1] - longest[0] < end - start) {
        longest = [start, end];
      }
    }
  }
  return s.slice(longest[0], longest[1] + 1);
};

O(n^2) 의 시간복잡도를 가지지만 pruning이 효율적으로 작용하기 때문에 확률적으로 훨씬 효율적이다.

2. Dynamic Programming

다른 방법을 찾아보니 DP를 이용한 풀이도 존재했다. 위와 같은 방법으로 어떤구간 isPalindrome[a][b]을 만족하고 s[a - 1] === s[b + 1]인 경우 isPalindrome[a - 1][b + 1]인 것을 알아낼 수 있다. 하지만 위의 방법이 더 효율적인 이유는 다음과 같다.

• 1번 방식은 pruning을 통해 a ~ b구간을 만족하지 않는다면 바깥 구간을 탐색하지 않지만 DP는 해당 구간을 탐색하고 만족하지 않는다는 것을 확인한다. => 같은 O(n^2)이라도 pruning이 적용 유무가 다르다.
• 1번 방식은 공간을 추가적으로 사용하지 않는다. DP는 start와 end 인덱스의 O(n^2)의 공간을 추가로 사용하게 된다.