dp로 풀수있고, dp의 공간복잡도 개선을 위해 투포인터로 풀수있다.
2d 배열을 DP 저장소로 사용한다.
다만, 대각선 오른쪽만 사용한다. 공간절반이 버려지는 셈이라 비효율적이다.
s[i]
, s[j]
가 같으면 s[i+1][j-1]
가 같은지 보면된다. 다르면 볼것도없이 그냥 0인거 건드리지않는다.index[i,j]
로 정답을 갱신한다.다만, aa와 같이 길이가 2개인 경우에는 s[i+1][j-1]
를 보면 엇갈려져서 정답로직에 예외가 생기므로 둘의 인덱스차이가 1인경우는 따로 빼주었다.
코드가독성을 위해 정답인 경우, getAnswer()
로 로직을 분리해주었다.
시간복잡도 O(N^2)
가 소요되고, 이를 저장할 어레이때문에 공간도 O(N^2)
가 소요된다.
var longestPalindrome = function(s) {
if(s.length===1) return s;
let max=1;
let index=[0,0];
const dp=[...Array(s.length)].map(r=>Array(s.length).fill(0));
const getAnswer=(i,j)=>{
max=j-i+1;
index[0]=i;
index[1]=j;
}
for(let i=s.length-1; i>=0; i--){
for(let j=s.length-1; j>=i; j--){
if(i===j){
dp[i][j]=1;
continue;
}
if(s[i]!==s[j]) continue;
if(j-i===1){
dp[i][j]=1;
if(max<j-i+1) getAnswer(i,j);
}
if(!dp[i+1][j-1]) continue;
dp[i][j]=1;
if(max<j-i+1) getAnswer(i,j);
}
}
return s.substring(index[0],index[1]+1);
};
dp테이블을 안쓰고 동적으로 하나씩 살펴보며 정답인지 체크하는 방식이다.
이 방식은 한계가 있는데, Palindrom이 홀수길이인지 짝수길이인지에 따라 다르게 생각해야한다.
aba 케이스(홀수)
가운데지점 b에서 시작해서 양옆으로 한칸씩 확장하며 비교하면 된다.
abba 케이스(짝수)
첫번째 b에서 시작해서 한칸씩 확장하면 팰린드롬인데도 아니라고 판단된다. 이 경우에는 시작하려는 인덱스의 한칸앞이 같은지도 확인해주고, 같다면 bb에서부터 양옆으로 한칸씩 확장하면 된다.
문제는 우리는 팰린드롬의 길이를 모르는 점인데, 그래서 홀짝케이스를 모두 가정하고 계산을 돌려버리고 두 방식의 결과 중 더 긴 걸 정답으로 치면 된다.
인덱스 0부터 시작점이라고 가정하고 양옆으로 뻗어나가고, 중간에 팰린드롬이 끊기면 시작인덱스를 증가시켜서 다시 뻗어나가길 반복한다. 결국 이중반복문으로 순회할 수 있다.
시간복잡도 O(N^2), 공간은 constant이므로 O(1)
var longestPalindrome = function(s) {
if(s.length===1) return s;
const getEven = (arr)=>{
const index=[0,0];
let max=1;
for(let i=0; i<arr.length; i++){
let l=i;
let r=i+1;
while(l>=0 && r<arr.length){
if(arr[l]!==arr[r]) break;
if(max <= r-l+1){
max=r-l+1;
index[0]=l;
index[1]=r;
}
l--;
r++;
}
}
return [index,max];
}
const getOdd = (arr)=>{
const index=[0,0];
let max=1;
for(let i=1; i<arr.length-1; i++){
let l=i;
let r=i;
while(l>=0 && r<arr.length){
if(arr[l]!==arr[r]) break;
if(max <= r-l+1){
max=r-l+1;
index[0]=l;
index[1]=r;
}
l--;
r++;
}
}
return [index,max];
}
const [evenIndex,evenLen] = getEven(s);
const [oddIndex,oddLen] = getOdd(s);
if(evenLen > oddLen) return s.substring(evenIndex[0],evenIndex[1]+1);
return s.substring(oddIndex[0],oddIndex[1]+1);
};
처음풀었을땐 손도못대로 솔루션보고 3일을 낑낑대고도 이해못했는데 이제 두가지 방식으로도 풀수있다니ㅠ감격ㅠ