LeetCode : 5. Longest Palindromic Substring

문제

문자열 $s$가 주어졌을 때, $s$의 부분 문자열 중 가장 긴 회문(Palindromic Substring)을 반환하라.

제약 조건

• $1 \le s$.length $\le 1000$
• $s$ 는 숫자와 영어 알파벳으로만 이루어져 있다.

예시

입력 : $s$ = "babad"
출력: "bab" 또는 "aba"

풀이

가장 처음 든 생각은 longestPalindrome 함수에서 모든 부분 문자열들을 생성해서 하나하나 회문인지 검사를 하고, 회문이 맞을 때 적당한 처리를 해줘야겠다는 것이었다. 그러기 위해서 회문인지 아닌지 검사하는 새로운 함수 isPalindrome 을 만들었고, 대략적인 의사코드는 다음과 같다.

FUNCTION isPalindrome(string) {
	// check if string is palindrome
}

FUNCTION longestPalindrome(string) {
	FOR all substrings:
    	IF isPalindrome(substring):
        	IF substring.length > max_length:
            	max_length = substring.length
                max_substring = substring
	RETURN max_substring
}

그럼 이제 가장 중요한 함수 isPalindrome 을 잘 구현하면 된다.

1. 문자열의 시작과 끝이 다르면 안에 어떤 문자가 들어있어도 회문이 아니다.

2. 회문의 구조를 보면 당연하게도 시작( string[0] ) 과 끝 문자( string[-1] )를 하나씩 제거했을 때도 남는 부분 문자열 (string[1:-1] )도 회문이라는 것을 알 수 있다.

isPalindrome 함수에서는 string[0] 과 string[-1] 이 같은지 검사한 뒤에
다시 자기 자신을 호출하면서 string[1:-1] 를 넘기면 된다.

이제 isPalindrome 함수를 어떻게 구현해야 하는지 감이 잡혔다.
이에 따라 의사코드를 업데이트하면 다음과 같다.

FUNCTION isPalindrome(string, start, end) {
	IF string[start] != string[end]:
    	RETURN false;
    ELSE:
	    IF isPalindrome(string, start+1, end-1) RETURN true;
        ELSE RETURN false;
}

1. 재귀 함수 구현

기저 사례를 최우선 처리

bool isPalindrome(string s, int start, int end) {
	//base case
    if(end <= start) return true;
    if(s[start] != s[end]) return false;
}

재귀 함수 구현

	if (isPalindrome(s, start+1, end-1) return true;
    else return false;

이렇게만 구현해놓으면 모든 $\frac{n(n+1)}{2}$ 개의 부분 문자열에 대해 회문 검사를 하고,
회문 검사의 시간 복잡도는 $O(n)$이므로 총 시간 복잡도는 $O(n^3)$가 된다.

이렇게 제출하면 역시나 Time Limit으로 인해 실패

2. Memoization 적용

• 먼저 계산 결과를 담아둘 cache 배열을 생성했고, 생성자에서 초기화를 진행하도록 하였다.

class Solution {
public :
	int cache[1001][1001];
    Solution() {
    	memset(cache, 0, sizeof(cache));
    }

• 이제 cache 배열을 참조해서 중복 계산을 줄이도록 변경

        int& ret = cache[start][end];

        if (ret == 1) return true;
        else if (ret == -1) return false;
        else if (ret == 0) {
            if (isPalindrome(s, start+1, end-1)) {
                ret = 1;
                return true;
            }
            else {
                ret = -1;
                return false;
            }
        }
        return false

3. Troubleshooting

Run을 하면 아무 문제가 없는데 Submit만 하면 이상하게 Memory Limit Exceeded 에러가 발생.

재귀 스택이 깊어짐에 따라 string s값을 계속 인자로 넘기는 것이 문제인가 싶어서 Call by Reference로 바꾸었더니 문제 해결.

bool isPalindrome(string& s, int start, int end)

4. 최종 코드

class Solution {
public:
    int cache[1001][1001];
    Solution() {
        memset(cache, 0, sizeof(cache));
    }

    bool isPalindrome(string& s, int start, int end) {
        // base case
        if(end <= start) return true;
        if(s[start] != s[end]) return false;

        int& ret = cache[start][end];

        if (ret == 1) return true;
        else if (ret == -1) return false;
        else if (ret == 0) {
            if (isPalindrome(s, start+1, end-1)) {
                ret = 1;
                return true;
            }
            else {
                ret = -1;
                return false;
            }
        }
        return false;
    }

    string longestPalindrome(string s) {
        int max_length = 1;
        string max_substring;
        max_substring = s[0];

        for(int start=0; start < s.length(); start++){
            for(int end=start; end < s.length(); end++){
                if (isPalindrome(s, start, end)) {
                    int substr_len = end-start+1;
                    if (substr_len > max_length) {
                        max_length = substr_len;
                        max_substring = s.substr(start, substr_len);
                    }
                }
            }
        }
        return max_substring;
    }
};

다른 풀이

놀랍게도 선형 시간내에 문제를 풀 수 있는 알고리즘이 존재한다.

• Manacher's algorithm
• Z algorithm

GeeksforGeeks에 잘 정리되어있어서 일단 링크를 걸어두고 시간이 되면 정리 해볼 예정!