[리트코드] 5. Longest Palindromic Substring

안녕하세요. 개발조각입니다.😊

이번 문제는 어려운 건 아닌데 풀다가 잘못 생각해서 헤맨ㅋㅋㅋ 그런 문제입니다.

---

https://leetcode.com/problems/longest-palindromic-substring/

Longest Palindromic Substring - LeetCode

 

해결방안

var longestPalindrome = function(s) {
    let str = '';
    let answer = s[0];
    for(let i=1; i<s.length; i++){        
        str = s[i];
        for(let j=1; j<=i; j++){
            let [prev, next] = [s[i-j], s[i+j]];
            
            if(prev === next){
                str = prev + str + next;
                if(str.length > answer.length) answer = str;
            }else{
                str = '';
                break;
            }
            
            if(j === i) str = '';
        }
    }
    
    let str2 = '';
    let answer2 = '';
    for(let i=1; i<s.length; i++){       
        for(let j=1; j<=i; j++){
            let [prev, next] = [s[i-j], s[i+j-1]];            
            if(prev === next){
                str2 = prev + str2 + next;
                if(str2.length > answer2.length) answer2 = str2;
            }else{
                str2 = '';
                break;
            }
            if(j === i) str2 = '';
        }
    }
    
    return answer.length > answer2.length ? answer : answer2;
};

이번 문제는 코드가 길긴 한데 이해하시면 쉽게 풀 수 있는 문제인 것 같아요.

 

코드를 보시면 두 가지로 나누어서 풀었습니다.

1. 회문(Palindrome) 문자열의 길이가 홀수 일 경우

prev

기준점

next

2. 회문(Palindrome) 문자열의 길이가 짝수 일 경우

prev-1

prev

기준점, next

next+1

 

크게 보면 기준점에 따라 비교하는 방식이랄까나

 

 

첫 번째 for문은 기준점을 찾기 위한 반복문이고

두 번째 for문은 기준점을 기준으로 기준점의 위치만큼 반복을 해주어 범위를 넓혀주는 방식입니다.

 

두 개가 구조는 비슷하지만

회문 문자열의 길이가 홀수, 짝수일 경우에 따라 조금 다르게 짰습니다.

 

1. 회문(Palindrome) 문자열의 길이가 홀수 일 경우

let str = ''; // j가 반복될 때마다 합쳐질 문자열
let answer = s[0];
for(let i=1; i<s.length; i++){        
    str = s[i];
    for(let j=1; j<=i; j++){
        let [prev, next] = [s[i-j], s[i+j]];

        if(prev === next){
            str = prev + str + next;
            if(str.length > answer.length) answer = str;
        }else{
            str = '';
            break;
        }

        if(j === i) str = ''; // 반복문이 끝나면 리셋
    }
}

 

2. 회문(Palindrome) 문자열의 길이가 짝수 일 경우

let str2 = '';
let answer2 = '';
for(let i=1; i<s.length; i++){       
    for(let j=1; j<=i; j++){
        let [prev, next] = [s[i-j], s[i+j-1]];            
        if(prev === next){
            str2 = prev + str2 + next;
            if(str2.length > answer2.length) answer2 = str2;
        }else{
            str2 = '';
            break;
        }
        if(j === i) str2 = '';
    }
}

 

 

return answer.length > answer2.length ? answer : answer2;

마지막으로 홀수일 경우 가장 긴 회문 문자열 길이와 짝수일 경우 가장 긴 회문 문자열을 비교하여

둘 중 긴 값을 반환해줍니다.