647. Palindromic Substrings

Medium

Given a string s, return the number of palindromic substrings in it.

A string is a palindrome when it reads the same backward as forward.

A substring is a contiguous sequence of characters within the string.

Example 1:

Input: s = "abc"
Output: 3
Explanation: Three palindromic strings: "a", "b", "c".
Plain Text
복사

Example 2:

Input: s = "aaa"
Output: 6
Explanation: Six palindromic strings: "a", "a", "a", "aa", "aa", "aaa".
Plain Text
복사

Constraints:

•

1 <= s.length <= 1000

•

s consists of lowercase English letters.

My solution

long palindrom 문제와 사실상 같은 문제다.

먼저 s[0]을 할당해두고 맨앞부터 연속적인 팰린드롬이 2글자짜리라면 그걸 시작점으로 삼는다.

이후 3자리이상부터는 검사할 때 미리 구해 놓은 첫번째 인덱스와 두번째 인덱스를 가지고 만들어낸다.

이때 중첩 for문이 복잡하다. i, j를 둘다 선언해야 한다.

따져보면 쉬운데, i는 0(처음)부터, j는 i + len - 1부터다. 즉, 길이를 맞추기 위해서 i를 더해준 것이다. 그만큼 우측으로 이동한 상태로 len-1을 세야하기 때문이다.

  for (let len = 3; len <= s.length; ++len) {
    for (let i = 0, j = i + len - 1; j < s.length; ++i, ++j) {
      dp[i][j] = dp[i + 1][j - 1] && s[i] === s[j];
      if (dp[i][j] && answer.length < len) {
        answer = s.substring(i, i + len);
      }
    }
  }
JavaScript
복사

둘다 1씩 증가시킨다.

const countSubstrings = function (s) {
  let answer = s[0];
  const n = s.length;
  const dp = [...Array(n)].map(() => [...Array(n)].fill(false));
  for (let i = 0; i < n; i++) {
    dp[i][i] = true;
  }

  // & : 맨앞부터 세서 2-substring인지 확인(default 1-substring)
  for (let i = 0; i < s.length - 1; ++i) {
    dp[i][i + 1] = s[i] === s[i + 1];
    if (dp[i][i + 1] && answer.length < 2) answer = s.substring(i, i + 2);
  }

  // & : 3자리부터 검사, (i + 1) ~ (j - 1)이 palindrome인지 이전 값을 통해 확인
  for (let len = 3; len <= s.length; ++len) {
    for (let i = 0, j = i + len - 1; j < s.length; ++i, ++j) {
      dp[i][j] = dp[i + 1][j - 1] && s[i] === s[j];
      if (dp[i][j] && answer.length < len) {
        answer = s.substring(i, i + len);
      }
    }
  }

  return dp.flat().filter(flag => flag).length;
};
JavaScript
복사

하지만 17%보다 빠르다. 성능이 마음에 안들어서 더 늘려보려고 한다. answer가 사실상 필요없다. dp 배열의 true값만 제대로 들어가면 구할 수 있기 때문이다.

하지만 for문이 성능의 문제를 일으키는 것 같다. 동일하게 17%보다 빠르다고 한다.

생각해보면 dp에 값을 할당할 때마다 cnt를 증가시키면 된다. dp를 굳이 flat해서 filter를 돌리고 length를 구할 필요가 없다.

따라서 cnt라는 변수를 만들어놓고 dp에 true가 할당되는 때마다 증가시켜서 반환해주었더니 아래와 같은 성능 개선이 되었다.

소스코드

/**
 * @param {string} s
 * @return {number}
 */
const countSubstrings = function (s) {
  const n = s.length;
  const dp = [...Array(n)].map(() => [...Array(n)].fill(false));
  let cnt = 0;

  for (let i = 0; i < n; i++) {
    dp[i][i] = true;
    cnt++;
  }

  // & : 맨앞부터 세서 2-substring인지 확인(default 1-substring)
  for (let i = 0; i < s.length - 1; ++i) {
    if (s[i] === s[i + 1]) {
      dp[i][i + 1] = true;
      cnt++;
    }
  }

  // & : 3자리부터 검사, (i + 1) ~ (j - 1)이 palindrome인지 이전 값을 통해 확인
  for (let len = 3; len <= s.length; ++len) {
    for (let i = 0, j = i + len - 1; j < s.length; ++i, ++j) {
      if (dp[i + 1][j - 1] && s[i] === s[j]) {
        dp[i][j] = true;
        cnt++;
      }
    }
  }

  return cnt;
};

test('TC1', () => {
  expect(countSubstrings('abc')).toStrictEqual(3);
});
test('TC2', () => {
  expect(countSubstrings('aaa')).toStrictEqual(6);
});
JavaScript
복사