[알고리즘] Longest Palindromic Substring

Leetcode의 Longest Palindromic Substring 문제를 풀어보도록 하겠습니다.

문제

주어진 문자열에서 가장 긴 회문(palindrome)을 찾아라. 문자열이 최대 길이는 1000이라고 가정한다.

예제

  • 입력: “babad” => 출력: “bab” 또는 “aba”

  • 입력: “cbbd” => 출력: “bb”

풀이

회문(palindrome)이란 앞에서부터 바로 읽으나 뒤에서부터 거꾸로 읽으나 같은 문자열을 의미합니다.
단순히 주어진 문자열이 회문인지를 검사할 때는 두개의 포인터를 이용하여 첫 포인터는 앞에서부터 뒤로 전진시키고 뒤 포인터는 뒤에서부터 앞으로 전진시키는 O(N) 알고리즘이 널리 사용됩니다.
하지만 이 문제는 주어진 문자열에서 만들어낼 수 있는 모든 부분 문자열이 회문인지를 알아내야 하는데 이를 위해서는 이중 루프가 필요하므로 O(N^2)번 O(N) 알고리즘을 돌려야합니다.
결국, O(N^3) 시간 복잡도를 가지는 알고리즘이 되는데 이러한 코드는 성능이 너무 떨어져서 Leetcode에서 Time Limit Exceeded 때문에 통과가 되지 않습니다.

곰곰히 생각을 해보면 위 접근 방법은 회문인지를 검사하는데 상당한 중복 연산이 일어납니다.
예를 들어, eve가 회문인지 알고 있는 상황에서는 level이 회문인지 검사할 때 첫 글자와 끝 글자가 동일한지만 체크하면 됩니다.
일반화하면, 어떤 부분 문자열의 시작 인덱스가 s, 끝 인덱스가 e라고 했을 때, s + 1에서 시작하고 e - 1에서 끝나는 문자열이 회문인지를 알고 있다면, se 인덱스에 위치하고 있는 문자가 동일하다면 회문이고, 동일하지 않다면 회문이 아니라는 것을 빠르게 알 수 있습니다.

위 알고리즘을 정리해보면,

If palindrome(s + 1, e - 1) and S[s] == S[e], then palindrome(s, e) is True.

그리고 문자열의 길이가 1이거나 2일 때는 다음과 같이 단순화 될 수 있습니다. 왜냐하면 문자열 길이가 1이면 무조건 회문이고, 문자열 길이가 2이면 두 문자가 동일할 때만 회문이기 때문입니다.

If s == e, then palindrome(s, e) is True.
If s + 1 == e and if S[s] == S[e], then palindrome(s, e) is True.

이런 방식으로 더 작은 문자열의 회문 검사 결과를 더 큰 문자열을 검사할 때 재활용하면 회문 검사에 소요되는 시간을 O(N)에서 O(1)으로 단축시킬 수 있습니다.
그리고 모든 부분 문자열의 회문 검사를 저장해놓을 자료구조가 필요한데 2차원 배열이나 시작, 끝 인덱스를 키로 갖는 해시테이블을 이용할 수 있습니다.

구현

다이나믹 프로그래밍 기법을 활용하여 2차원 배열에 회문 검사를 짧은 문자열부터 긴 문자열 순서로 저장해 나가겠습니다.
일단 모든 부분 문자열을 구하기 위해서 이중 루프로 모든 가능한 시작 인덱스와 끝 인덱스의 조합을 만들어내야 합니다.
그리고 각 시작, 끝 인덱스 쌍에 대해서 자료구조에 회문인지를 더 짧은 문자열의 검사 결과를 재활용하여 검사하여 그 결과를 다시 더 큰 문자열을 위해서 자료구조에 저장해줘야 합니다.

최종적으로 리턴해야하는 값이 가장 긴 회문의 길이이기 때문에 변수를 하나 선언하여 막 발견한 회문의 길이가 여태까지 발견한 회문의 길이보다 길다면 업데이트를 해줍니다.

다이나밍 프로그래밍을 이용하여 코딩을 할 때 반목문의 진행 순서가 매우 중요합니다.
기존 계산 값을 재활용하기 위해서 외부 루프는 뒤에서 앞으로 내부 루프는 앞에서 뒤로 진행하기 있다는 점에 유의바랍니다.

Python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
def longestPalindrome(self, text: str) -> str:
palindrome = ''
length = len(text)
dp = [[False] * length for _ in range(length)]
for s in range(length - 1, -1, -1):
for e in range(s, length):
if s == e or (s + 1 == e and text[s] == text[e]):
dp[s][e] = True
else:
dp[s][e] = dp[s + 1][e - 1] and text[s] == text[e]
if dp[s][e] and len(palindrome) < e - s + 1:
palindrome = text[s: e + 1]
return palindrome

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public String longestPalindrome(String text) {
String palindrome = "";
int length = text.length();
boolean[][] dp = new boolean[length][length];
for (int s = length - 1; s > -1; s--) {
for (int e = s; e < length; e++) {
if (s == e || (s + 1 == e && text.charAt(s) == text.charAt(e)))
dp[s][e] = true;
else
dp[s][e] = dp[s + 1][e - 1] && text.charAt(s) == text.charAt(e);
if (dp[s][e] && palindrome.length() < e - s + 1)
palindrome = text.substring(s, e + 1);
}
}
return palindrome;
}
}

복잡도

위 코드는 이중 루프와 2차원 배열을 사용하고 있습니다.
따라서 N을 문자열의 길이라고 했을 때, 다음과 같은 복잡도를 가집니다.

  • 시간: O(N^2)
  • 공간: O(N^2)

문제 출처

공유하기