5. Longest Palindromic Substring

dp로 풀수있고, dp의 공간복잡도 개선을 위해 투포인터로 풀수있다.

풀이 1. Dynamic Programming

2d 배열을 DP 저장소로 사용한다.
다만, 대각선 오른쪽만 사용한다. 공간절반이 버려지는 셈이라 비효율적이다.

1. 모두 초기값 0으로 설정해두고 오른쪽 아래부터 왼쪽위로 순회한다.
2. 현재 인덱스 i와 j에 대해 s[i], s[j]가 같으면 s[i+1][j-1]가 같은지 보면된다. 다르면 볼것도없이 그냥 0인거 건드리지않는다.
3. 같다면 정답을 갱신해야하는데, 현재 max길이보다 크면 index[i,j]로 정답을 갱신한다.

다만, aa와 같이 길이가 2개인 경우에는 s[i+1][j-1]를 보면 엇갈려져서 정답로직에 예외가 생기므로 둘의 인덱스차이가 1인경우는 따로 빼주었다.

코드가독성을 위해 정답인 경우, getAnswer()로 로직을 분리해주었다.

Time, Space complexity

시간복잡도 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);
};

풀이 2. Two Pointer

dp테이블을 안쓰고 동적으로 하나씩 살펴보며 정답인지 체크하는 방식이다.

이 방식은 한계가 있는데, Palindrom이 홀수길이인지 짝수길이인지에 따라 다르게 생각해야한다.

• aba 케이스(홀수)
  가운데지점 b에서 시작해서 양옆으로 한칸씩 확장하며 비교하면 된다.

• abba 케이스(짝수)
  첫번째 b에서 시작해서 한칸씩 확장하면 팰린드롬인데도 아니라고 판단된다. 이 경우에는 시작하려는 인덱스의 한칸앞이 같은지도 확인해주고, 같다면 bb에서부터 양옆으로 한칸씩 확장하면 된다.

문제는 우리는 팰린드롬의 길이를 모르는 점인데, 그래서 홀짝케이스를 모두 가정하고 계산을 돌려버리고 두 방식의 결과 중 더 긴 걸 정답으로 치면 된다.

인덱스 0부터 시작점이라고 가정하고 양옆으로 뻗어나가고, 중간에 팰린드롬이 끊기면 시작인덱스를 증가시켜서 다시 뻗어나가길 반복한다. 결국 이중반복문으로 순회할 수 있다.

Time, Space complexity

시간복잡도 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일을 낑낑대고도 이해못했는데 이제 두가지 방식으로도 풀수있다니ㅠ감격ㅠ