[리트코드] 647. Palindromic Substrings




647. Palindromic Substrings

리트코드

나의 풀이 (런타임 에러)

/**
 * @param {string} s
 * @return {number}
 */

const isPalindrom = s => {
  return s === [...s].reverse().join('');
};
var countSubstrings = function (s) {
  let num = 0;
  for (let i = 0; i < s.length; i++) {
    for (let j = i + 2; j <= s.length; j++) {
      if (isPalindrom(s.substring(i, j))) num++;
    }
  }
  return num + s.length;
};


한 개인 경우는 isPalindrom을 거치지 않고, 따로 분리하였다.
하지만 테스트케이스 문자열이 너무 길어서 런타임 에러가 났다.




효율성 좋은 코드

/**
 * @param {string} s
 * @return {number}
 */


let countPalindrome = (l, r, s) => {
    let result = 0;
    while (l >= 0 && r < s.length && s[l] === s[r]) {
        result++;
        l--;
        r++;
    }
    return result;
}

var countSubstrings = function(s) {
    let result = 0;
    
    for (let i = 0; i < s.length; i++) {
        result += countPalindrome(i, i, s);
        result += countPalindrome(i, i + 1, s);
    }
    
    return result;
};

투 포인터를 활용한 방법이다.
문자열이 홀수개일 때 : i를 기준으로 양옆으로 뻗어나가면서 확인
문자열이 짝수개일 때 : i,j를 기준으로 양옆으로 뻗어나가면서 확인
팰린드롬을 확인하는 새로운 방법인 것 같다.!👍

Runtime: 96 ms, faster than 56.39% of JavaScript online submissions for Palindromic Substrings.