Longest Palindrome

가장 큰 펠린드롬을 찾는 문제이다.

worst case

그냥 떠오르는데로 문제를 풀었더니, 시간초과발생. O(n^3)

//brute force
    
    // check palindrome n
    function isPanlin(str){
        return str === str.split("").reverse().join("");
    }

    let answer;
    let max = 0;
    let idx = 0;

	// n^2
    for(let idx = 0;idx<s.length;idx++){
        if(max >= s.length - (idx)){
           break;
        }
        for(let check=s.length;check>=idx;check--){
            let tar = s.substring(idx,check)           
            if(isPanlin(tar) ){
                // 회문검사 비용이 너무크다 이를 디피로 줄여야함
                if(max < tar.length){
                    answer = tar;
                    max = tar.length;
                }
            }
        }
    }

위 코드는 문자열을 n^2번 순회하면서 나오는 문자열을 펠린드롬 체크함수에 넣어 체크한 후 가장 크면 저장하는 방식의 코드이다.(Brute Force)

return string.split('').reverse().join('') 이 코드가 O(n+k)의 복잡도를 가짐

// Time Complexity = Possibly O(n+k)
// Since these are inbuilt methods, we can't be 100% sure of how
// JavaScript is handling them. But since .reverse() involves
// traversing through an array, it possibly has time complexity
// of O(n).
// So we can represent the time complexity as O(n+k), where k is a
// constant to heuristically denote the complexity of the other two
// methods.

n^2까지는 어쩔 수 없음. 펠린드롬 검사를 O(n) -> O(1)로 줄여야한다.

Success Case

Dynamic Programming의 방식을 적용

펠린드롬은 앞뒤가 같으면서 앞 뒤를 자른 나머지 안의 문자들이 회문이면 회문이다. 이것에서 아이디어를 얻어 디피 방식으로 생각해보면 다음과 같이 구현할 수 있다.

문자가 두개인 경우 -> 문자가 세개인 경우 -> ... 로 나아가면서 회문인지 아닌지 점검한다.

EX)
문자열 s가 abba인 경우, i=0 j=3라면, s[0] === s[3] && dp[1][2]가 회문이면(true 이면) dp[0][3]은 회문이다.(true이다 )

  let dp = []
    // 문자가 한개인 경우 펠린드롬이다.
    // dp[0][3]은 0~3의 문자열의 회문인지 아닌지를 값으로 저장한다.
  	for(let check=0;check<s.length;check++){
        dp[check]= Array(s.length).fill(false);
        // character is palindromic
        dp[check][check] = true;
    }
    let left = 0;
    let right = 0;
    for(let i=1;i<s.length;i++){
 		// 두개인 경우 -> 세 개인 경우 -> ... 로 나아가며 점검한다.
      
        let j=0;
        while(j+i < s.length){
            if(s[j] === s[j+i]){
              // 앞 뒤 문자가 같으면 펠린드롬일 수 있다.
              
              
                if(i === 1 || dp[j+1][j+i-1]){
                  // 문자가 두개인 경우 또는 앞뒤를 짜른 문자열이 회문인 경우
                  // is Pelindromic
                  dp[j][j+i] = true;
                  
                  // 시작할 문자열 인덱스와 끝날 문자열 인덱스를 저장한다.
                  // 문자가 한개인 경우부터(작은 경우부터) 나아가므로 이 곳에 마지막으로 들어와 저장된 값이 최대 펠린드롬의 인덱스 번호들임.
                  left = j
                  right = j+i
                }
            }
            j++;
        }
    }

    
    return s.slice(left,right+1)   

DP와 재귀를 이용하지 않은 코드

 function getPelinIndex(type,i){
        switch(type){
            case 'even':
                if(s[i] !== s[i+1]){
                  // 짝수로 호출되었는데 중앙 데이터들의 값이 다르다면 회문이 아니므로, 그 문자를 회문으로 리턴한다.
                    left = i;
                    right = i;
                    return [left,right];
                    
                }else{
                  // 짝수인데 중앙 데이터들의 값이 같다면 회문 일 수 있으므로 리턴하지 않는다.
                  // O O O<-(이거말하는거임)->O O O 
                    left = i;
                    right = i + 1;
                }
                break;
                
            case 'odd':
              	// 홀수로 호출하였다면 O O O<--(이거말하는거임) O O 
                left = i;
                right = i;
                break;
        }
        
         while(left>0 && right < s.length && s[left-1] === s[right+1]){
                  // left는 줄이고
           		  // right는 올리면서 서로의 값이 같은지 확인한다.(회문조건임)
           		  // O O O O O O 
                  left--;
                  right++;
         }
        
        return [left,right]
       
    }
    let left;
    let right;
    let maxRight = 0;
    let maxLeft = 0;
    for(let i=0;i<s.length-1;i++){
     
        // even
        [left,right] = getPelinIndex('even',i)
        
        if(maxRight-maxLeft < right - left){
          // Return한 문자열의 길이가 맥스 값보다 길다면 바꾼다.(최대를 찾아야하므로)
            maxRight = right;
            maxLeft = left;            
        }
        // odd
        
        [left,right] = getPelinIndex('odd',i)
        
        if(maxRight-maxLeft < right - left){
          // Return한 문자열의 길이가 맥스 값보다 길다면 바꾼다.(최대를 찾아야하므로)
          
            maxRight = right;
            maxLeft = left;            
        }
        
    }
    return s.slice(maxLeft,maxRight+1)