리트코드 5번: Longest Palindromic Substring

문제
Given a string s, return the longest palindromic substring in s.
(앞에서부터 읽어도 뒤에서부터 읽어도 같은 문자열 중 가장 긴 문자열 찾기)

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

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

 

내 풀이

내 생각의 흐름
1. 음... 모르겠다
2. 힌트를 보자. https://youtu.be/UflHuQj6MVA 영상을 보고 깨달음을 얻음
3. 후다닥 구현

/**
 * @param {string} s
 * @return {string}
 */
var longestPalindrome = function (s) {
    const memo = Array.from(Array(s.length), () => new Array(s.length).fill(false))
    let result = ''

    for (let i = 0; i < s.length; i++) {
        memo[i][i] = true;
        result = s[i];
    }

    for (let len = 2; len <= s.length; len++) {
        for (let i = 0; i + len - 1 < s.length; i++) {
            const start = i;
            const end = i + len - 1;

            memo[start][end] = s[start] === s[end] && (end - start <= 1 || memo[start + 1][end - 1])

            if (memo[start][end] && end - start + 1 > result.length) {
                result = s.substring(start, end + 1)
            }
        }
    }

    return result
};

 

시간 복잡도
첫번째 루프는 s.length에 선형적으로 비례하므로 O(n)의 시간 복잡도를 가진다.
두번째 중첩 루프는 s.length에 대해 중첩으로 반복하므로 O(n^2)의 복잡도를 가진다.
정리하면, 전체 시간 복잡도는 O(n) + O(n^2) = O(n^2)

공간 복잡도
n x n 크기의 2차원 배열인 memo는 O(n^2)의 공간 복잡도를 가진다.
result는 s.length에 영향을 받으므로 O(n)의 복잡도를 가지지만, memo에 비해 상대적으로 무시할 수 있다.
정리하면, 공간 복잡도는 O(n^2)

---

고수의 풀이

Dynamic Programming, DP
고수의 말에 의하면 이 문제는 DP 기법을 이용해 풀어야한다.
DP는 일종의 문제 해결 패러다임으로 문제를 해결하기 위해 문제를 더 작은 문제로 쪼개서 생각하고 앞에서 구한 값을 뒤에서 재사용하는 방식이다.

분할 정복: 문제를 더 작은 문제로 쪼개서 생각하라는 의미를 5번 문제의 예시로 설명해보면,
babad의 가장 긴 회문 문자열을 찾는 것은 aba의 가장 긴 회문 문자열 앞, 뒤로 'b', 'd'를 붙이는 것이고
aba의 가장 긴 회문 문자열을 찾는 것은 b의 가장 긴 회문 문자열 앞, 뒤로 'a', 'a'를 붙이는 것이다.
b 문자열의 길이는 1이므로 b의 가장 긴 회문 문자열은 'b'가 된다.

메모이제이션: 앞에서 구한 값을 뒤에서 재사용하라는 의미는, 
aba의 가장 긴 회문 문자열은 'aba' 라는 걸 이미 구했다면,
babad의 가장 긴 회문 문자열을 찾는 것은 앞에서 구한 가장 긴 회문 문자열 'aba'의 앞 뒤로 'b', 'd' 를 붙여 회문이 성립하는지만 확인해보면 된다. 굳이 aba의 회문 문자열을 또 다시 찾는 과정을 겪을 필요가 없다.

고수의 생각의 흐름 ver. Expand Around Center
1. 회문이 성립하려면 중심을 기준으로 문자가 대칭을 만들어야 한다.
2. s[0...length]를 순회하면서 index를 기준으로 양 옆에 문자를 추가하면서 회문인지를 확인해보자.
3. 회문의 길이가 홀수인 경우에는 2번 방식을 이용할 수 있지만 길이가 짝수라면?
4. 짝수의 경우에는 index를 기준으로 s[index]와 s[index+1]이 같은지, s[index-1]과 s[index+2]가 같은지 확인해보자. 
5. 회문이 성립되는 start index와 end index를 이용해서 가장 긴 회문 문자열을 찾자.

 

 

고수의 생각의 흐름을 이해한 후 다시 짠 코드

/**
 * @param {string} s
 * @return {string}
 */
var longestPalindrome = function (s) {
    let range = [0, 0];

    for (let i = 0; i < s.length; i++) {
        // 회문의 길이가 홀수일 때
        const [startByOdd, endByOdd] = findLongestPalidromeRange(s, i, i)

        if (range[1] - range[0] < endByOdd - startByOdd) {
            range = [startByOdd, endByOdd]
        }

        // 회문의 길이가 짝수일 때
        const [startByEven, endByEven] = findLongestPalidromeRange(s, i, i + 1)

        if (range[1] - range[0] < endByEven - startByEven) {
            range = [startByEven, endByEven]
        }


    }

    return s.substring(range[0], range[1] + 1)
};

var findLongestPalidromeRange = function (s, start, end) {
    while (start >= 0 && end < s.length && start <= end && s[start] === s[end]) {
        start--;
        end++;
    }

    return [start + 1, end - 1]
}