[리트코드] 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.