.png&blockId=5f7573ad-6867-4d59-999e-722aced04aeb)
가장 긴 팰린드롬 부분 문자열을 출력하라.
My solution
s[i] === s[j] && (i - j < 3 || dp[j + 1]) //일단 팰린드롬인데, 이전도 팰린드롬인지가 && 다음 문
JavaScript
복사
dp로 확인되면 dp[j]=1;이 된다.
그리고 이번 팰린드롬 문자열이 가장 긴지 max로 확인한 뒤 그렇다면 max와 start가 업데이트된다.
Code
const longestPalindromeSubstring = function (s) {
const dp = Array(s.length).fill(0);
let max = 0;
let startIdx = 0;
for (let len = 0; len < s.length; len++) {
for (let start = 0; start <= len; start++) {
if (s[len] === s[start] && (len - start < 3 || dp[start + 1])) {
dp[start] = 1;
if (len - start + 1 > max) {
max = len - start + 1;
startIdx = start;
}
}
}
}
return s.slice(startIdx, startIdx + max);
};
JavaScript
복사
단점은 dp자체가 난이도가 높기도 하지만 가독성도 좋지 않다고 느껴진다. 로직을 봤을 때 바로 이해가 되지는 않는다. i와 j를 len(길이), start(시작인덱스)로 바꾸어서 그나마 낫다.
Solution
1. 중앙을 중심으로 확장하는 풀이
dp는 가능하지만 직관적으로 이해하기 어렵고 실행 속도가 느리다. 투포인터가 낫다.
2칸과 3칸으로 구성된 투포인터를 쓴다.
팰린드롬이 발견되면 멈춰서 투포인터를 점점 확장한다.
bb일 때(짝수)도, bab일 때(홀수)도 있다.
(위의 예는 짝수 투포인터는 무시될 것이다.)
또한, 1개짜리 문자열이거나 전체가 팰린드롬이면 edge case 처리하면 성능이 개선된다.
expand함수에 left, right 포인터를 넣어줘서 검사하므로 가독성도 좋다.
js로 아래처럼 구현 가능하다.
// two pointer
const longestPalindromeSubstring = function (s) {
function expand(left, right) {
let lt = left;
let rt = right; // no reassign func parameter
while (lt >= 0 && rt < s.length && s[lt] === s[rt]) {
lt--;
rt++;
}
return s.slice(lt + 1, rt);
}
if (s.length < 2 || s === s.split('').reverse().join('')) return s;
let result = ['', 0];
for (let i = 0; i < s.length; i++) {
const odd = expand(i, i);
const even = expand(i, i + 1);
const cur = odd.length > even.length ? odd : even;
if (cur.length > result[1]) {
result = [cur, cur.length];
}
}
return result[0];
};
JavaScript
복사
파이선은 max함수에 key=len을 줄 수 있어서 len으로 비교만하고 그 문자열을 꺼내올 수 있지만
js에서는 length를 기준으로 비교만 하고 원래 그 문자열을 리턴할 수 없다. 따라서 result 를 팰린드롬과 그 길이로 구성된 배열의 형식(['', 0])으로 만들어주었다.
