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までは仕方ありません.PhilyndromチェックをO(n)->O(1)に減らす必要があります.

Success Case

ダイナミックプログラミングを適用する方法
フェリンドロムは前後が一致して、前後を切って、中の文字は回文で回文です.そこからいくつかの考えを得て、数字の方式で考えて、以下のように体現することができます.
2文字ある場合->3文字ある場合->上へ行って、会文の有無をチェックします.
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)