스터디 4주차 / leetcode / Longest Palindromic Substring / JavaScript

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

Longest Palindromic Substring - LeetCode

Given a string s, return the longest palindromic substring  in s.

 

Example 1:

Input: s = "babad"
Output: "bab"
Explanation: "aba" is also a valid answer.

Example 2:

Input: s = "cbbd"
Output: "bb"

 

Constraints:

• 1 <= s.length <= 1000
• s consist of only digits and English letters.

주어진 s 문자열 안에서 좌우가 대칭이 되는 하위 문자열중에 가장 길이가 긴 부분을 찾아내는 문제였습니다.

특별한 개념을 사용하는 문제가 아닌 생각이 들어서 아이디어만 잘 떠올리면 될 것 같아 열심히 풀어보았는데,

답을 도출해내기가 상당히 어려웠습니다,, 시도할만큼 했다고 생각하여 다른분들의 솔루션을 참고해봤습니다.

 

여러 솔루션을 봐도 풀이 코드를 이해하기가 정말 어려웠습니다. 그래서 가장 반응이 좋았던 솔루션 하나를 선택해서 

여러번 반복해서 보면서 이해하려고 노력했고, 어느 정도 이해를 했다고 생각하지만 100% 옳게 이해한것인지 확신이

들지는 않습니다. 그래도 정말 많은 도움이 되었고 제가 이해한대로 설명을 적어보겠습니다.

 

const FindLongestPalindrome 변수에 들어가 있는 함수의 아이디어는 정말 유익한 것 같습니다.

s에 문자하나를 기준으로 왼쪽으로 한칸 오른쪽으로 한칸 이동하면서 비교를 해가며 대칭이 아니라면

지금까지 검사했던 문자열을 잘라 반환해주는 함수입니다. 아래의 코드는 이 함수를 활용하여 문제를 해결할 예정입니다.

 

for문으로 이제 입력으로 받는 s문자열의 첫번째 인덱스부터 검사를 시작합니다.

여기서 중요한 포인트는 current1과 current2 두개의 변수로 모든 경우의 수를 잡는 부분이라고 생각합니다.

만약 current1만 있었다면, s가 baab 일때 답으로 baab를 도출해내지 못합니다. current2를 사용해야 비로소 baab같은 입력에도 답을 캐치할 수 있습니다. 즉, 문자 단 1개만 검사를 하는 것과 문자 2개를 하나로 보고 검사를 하는 것 모두를 사용하여 놓칠 수 있는 경우의 수를 모두 검사해주고 있습니다. 3개 이상을 하나로 묶어서 하는 경우의 수는 왜 검사를 안할까라는 의문을 스스로 갖기도 했었는데, 3개 이상의 경우들은 위의 1개와 2개를 검사하는 경우에서 포함이 되기 때문에 따로 할 필요가 없습니다. 이미 저 두개의 경우에서 모든 경우의 수를 잡아낼 수 있기 때문에 그 이상의 것은 필요하지 않습니다.

그렇게 탐색하여 얻어낸 좌우 대칭의 substring들의 크기를 비교하면서 longestStr에 저장하여 가장 길이가 긴 하위 문자열을 반환하여 정답을 도출하는 코드였습니다.

 

기가막힌 아이디어라는 생각이듭니다,, 좌 우로 한칸씩 이동하여 문자열을 탐색하는 함수의 아이디어와 모든 경우의 수를 탐색하기 위해 current1과 current2를 사용하는 부분까지 완벽한 코드였다고 생각합니다. 여러번 곱씹어 보며 공부해서 사소한 부분 하나까지도 완벽히 이해하도록 노력해봐야 할 것 같습니다.

/**
 * @param {string} s
 * @return {string}
 */
var longestPalindrome = function(s) {
    let longestStr = '';
    const FindLongestPalindrome = (str, i, j) => {
        while (i>=0 && j<str.length && str[i] === str[j]){
            i -= 1;
            j += 1;
        }
        
        return str.slice(i+1 , j);
 
    }
 
    for (let i=0; i<s.length; i++){
        const current1 = FindLongestPalindrome (s, i, i);
        const current2 = FindLongestPalindrome (s, i, i+1);
        
        const nowCurrent = current1.length > current2.length ? current1 : current2;
 
        if (longestStr.length < nowCurrent.length){
            longestStr = nowCurrent;
        }
    }
 
    return longestStr;
};

 

참고한 솔루션 : https://leetcode.com/problems/longest-palindromic-substring/solutions/548834/intuitive-javascript-solution-with-expand-around-center/?languageTags=javascript