647. Palindromic Substrings

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

Solution

Set middle and expand

한 문자열에서Palindrom을 판별하기 위해서는 최소한 모든 문자를 식별해야 되기 때문에 O(n)의 시간이 걸린다. 하지만 한 문자열이 이미 Palindrom을 만족한다면 그 좌우로 같은 문자가 존재하는지를 확인함으로서 O(1)의 시간으로 추가적인 Palindrom을 판별할 수 있다. 이러한 성질을 이용해 가운데 문자를 정한다면 최대 길이의 Palindrom을 구하는데 O(n)의 시간복잡도로 구할 수 있게 된다.

Algorithm

• middleToPalindromCount는 가운데 값을 정해놓고 만들 수 있는 Palindrom의 개수를 리턴한다.
• 기존의 범위가 Palindrom일 경우 좌우로 같은 문자가 존재할 경우 그 범위를 넓히는 방식으로 최대한 넓혀서 가능한 경우의 수를 구한다.
• 가운데 문자의 조건은 1개일 때와 같은 연속된 문자 2개일 경우 모두 가능하기 때문에 이를 모두 탐색한다.
• result에 모든 가운데 기준으로 연산한 Palindrom개수들을 더해 전체 Palindrom의 개수를 구한다.

var countSubstrings = function(s) {
  // Set middle and expand
  // 1. Set middle(one or two)
  // 2. Expand to maximum palindrom => get possible palindorm count
  const middleToPalindromCount = (start, end) => {
    if (s[start] !== s[end]) return 0;
    
    // Expand to maximum palindorm
    while (s[start - 1] === s[end + 1] && s[start - 1]) {
      start--;
      end++;
    }
    
    return Math.floor((end - start + 2) / 2);
  }
  
  let result = 0;
  for (let i = 0; i < s.length; i++) {
    result += middleToPalindromCount(i, i);
    result += middleToPalindromCount(i - 1, i);
  }
  return result;
};

위 방식은 DP로도 구현이 가능하다. 같은 O(n^2)의 시간복잡도를 사용하지만 위 방식은 더 이상 연산할 필요가 없는 부분은 아예 안하는 pruning을 해 효율적이다. 공간적으로도 O(1)만 사용하며 DP의 경우 O(n^2)의 공간을 할당해 주어야 한다.