Longest Palindromic Substring

Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.

Input: "babad"
Output: "bab"
Note: "aba" is also a valid answer.

Input: "cbbd"
Output: "bb"

 

생각의 흐름

일단 가장 쉬운 풀이를 생각해보았다. 시작점과 길이를 바꿔가면서 2중 for문으로 풀면 풀릴것같았다. 다만 중복 계산이 너무 많다. 이전에 계산했던 결과를 이용하면 그 다음 문제를 해결하는데 사용할 수 있다.

 

어떻게 하면 중복 계산을 제거할 수 있을까 고민하던 찰나에, 팰린드롬의 특성을 이용해보자는 생각이 들었다. 팰린드롬은 양끝을 제외한 가운데 부분이 팰린드롬이고 양끝이 같으면 그 부분은 팰린드롬이다. 이 점을 이용하면 중복 계산을 줄일 수 있을거란 생각이 들었다.

 

우선 2차원 배열을 선언한뒤, 시작점과 길이를 계속 바꿔가면서 문자열의 시작 인덱스와 끝 인덱스로 잘랐을때 해당 부분이 팰린드롬인지를 아닌지를 기록했다.

 

그럼 길이가 2일때 구해놨던 정보들이 길이가 3일때 해당 부분이 팰린드롬인지 판단할때 중복계산을 막아 줄 수 있기 때문에 어느정도 계산량을 줄일 수 있었다. 다만 이렇게 해도 퍼센티지가 너무 낮은걸 보니 별로 좋지 못한 풀이인것같다.

 

var longestPalindrome = function(s) {
    const dp = Array(s.length).fill(true).map(() => Array(s.length).fill(true));
    let resultLeft=0, resultRight=0;
    let MAX = 1;

    for(let len=2; len<=s.length; len++) {
        for(let left=0; left<=s.length - len; left++) {
            const right = left + len - 1;
            if(s[left] === s[right] && dp[left+1][right-1]){
                dp[left][right] = true;

                if(MAX < right - left + 1) {
                    MAX = right - left + 1;
                    resultLeft = left;
                    resultRight = right;
                }
            } 
            else {
              dp[left][right] = false;  
            } 
        }
    }

    return s.slice(resultLeft, resultRight+1);
};