[LeetCode 5] Longest Palindromic Substring (Java)

---

풀이

1. 브루트 포스

이 문제는 문자열 s가 주어졌을 때, s안의 가장 긴 팰린드롬 부분 문자열을 구하는 문제이다.

정말 단순히 생각하자면 부분 문자열을 정한 뒤, 팰린드롬인지 판단하면 될 것 같다. 이 풀이는 시간복잡도가 $O(N^2)$으로, 문제 조건인 $1 \le N \le 1000$ 범위에서는 시간초과가 발생하지 않을 것 같아보인다.

하지만 팰린드롬이 아니라면, result에 부분 문자열을 저장하는 과정이 추가로 들어가기 때문에 정확한 시간복잡도는 $O(k \times N^2)$가 될 것이다. 따라서, 시간 초과가 발생할 수 있으니 이 풀이는 적절하지 않다.

2. 확장하여 팰린드롬 구하기

문자열 s가 주어졌을 때, 인덱스 i부터 인덱스 j까지가 팰린드롬이라고 가정하고 풀이를 진행해보자.

이 상황이라면 우리는 이 부분 문자열을 확장하여, 이것이 팰린드롬인지 확인할 수 있을 것이다.
즉, 인덱스 i - 1부터 인덱스 j + 1까지가 팰린드롬인지 확인하자는 의미이다.

이렇게 접근한다면, 시작 위치만 정해주면 부분 문자열을 확장해가며 팰린드롬인지 확인할 수 있게 된다.

따라서 이 풀이는 시간복잡도가 $O(k \times N)$이 된다. 즉, 이 풀이는 시간 초과가 발생하지 않으므로 이를 코드로 구현하면 정답이 된다.

class Solution {
    int left, maxLen;

	// 부분 문자열이 팰린드롬이라면 확장하여, 부분 문자열의 시작 위치와 최대 길이를 구하는 함수
    private void expendPalindrome(String s, int i, int j) {
        while (i >= 0 && j < s.length() && s.charAt(i) == s.charAt(j)) {
            i--;
            j++;
        }

		// 반복문을 탈출하였으므로, i와 j가 범위를 벗어났거나 `s.charAt(i) != s.charAt(j)`일 것이다.
        // 따라서, 유효한 팰린드롬 부분 문자열은 i + 1부터 j - 1까지일 것이다.
        // 그러므로, 문자열의 길이는 j - i - 1, 시작 위치는 i + 1일 것이다.
        if (maxLen < j - i - 1) {
            left = i + 1;
            maxLen = j - i - 1;
        }
    }

    public String longestPalindrome(String s) {
        for (int i = 0; i < s.length(); i++) {
        	// 시작 위치가 i부터 i까지인 것은 size가 1인 부분 문자열임 -> 홀수 길이만 체크
            expendPalindrome(s, i, i);
            // 시작 위치가 i부터 i + 1까지인 것은 size가 2인 부분 문자열임 -> 짝수 길이만 체크
            expendPalindrome(s, i, i + 1);
        }
        return s.substring(left, left + maxLen);
    }
}