leetcode. Longest Substring Without Repeating Characters

문제

요약

문자열 s가 주어지면, s내에서 가장 긴 회문을 출력하라

풀이

/**
 * @param {string} s
 * @return {string}
 */
var longestPalindrome = function(s) {
    for(let i=s.length; i>0;i--){
        for(let j=0;j+i<=s.length;j++){
            if(checkPalindrome(s.slice(j,j+i))) return s.slice(j,j+i);
        }
    }
};

function checkPalindrome(str){
    for(let i=0; i<str.length/2;i++){
        if(str[i] !== str[(str.length-1)-i]) return false;
    }
    return true;
}

딱히 설명이 필요없는 브루트 포스로 해결한 문제다

Discuss

다른 사람들과 비교해보니 말도 안되게 빠른 해답들이 있어서 한번 살펴봤다

회문을 찾는 알고리즘이 따로 있었다 이 증명을 이해해야하는데 이건 나중에..

Python O(n^2) method with some optimization, 88ms. - LeetCode Discuss

그래서 이해는 포기하고 작동 원리만 배워왔다

1. 문자열에서 1글자 또는 2글자씩만 검사한다
2. 1번에서 검사한 글자들이 회문이라면 글자를 좌우로 확장시킨다
3. 확장시킨 글자가 회문이 아닐 때 까지 2를 반복한다
4. 가장 긴 회문을 구한다

여기서 1번에서 1글자 또는 2글자만 검사한다는 것은 abcdef의 문자열이 있을 때

i = 0, a와 ab가 회문인지
i = 1, b와 bc가 회문인지
i = 2, c와 cd가 회문인지
...
로 이해하면 된다

var longestPalindrome = function(s) {
    var str = '';
    for (let i = 0; i < s.length; i++) {
        if(i>s.length/2 && s.length-i<str.length) {
            console.log(i);
            console.log(s.length);
            break;
        }
        for (let j = 0; j < 2; j++) {
            var left = i;
            var right = left + j;
            while (s[left] && s[left] === s[right]) {
                left--;
                right++;
            }
            if (right - left - 1 > str.length) {
                str = s.slice(left + 1, right);
            }
        }
    }
    return str;
};

와 같이 구현할 수 있다