https://leetcode.com/problems/longest-palindromic-substring/
가장 긴 팰린드롬 문자열을 찾아내는 문제로, 팰린드롬 문자열이란 뒤집어도 똑같은 글자가 나오는 것을 의미한다.
대표적으로 기러기, 삐삐, 이효리(아님) 같은 것들이 해당된다.
한 글자도 팰린드롬이다.
가장 쉬운 방법은 3중 반복문을 활용하는 것이고, 시간복잡도를 제한하는 문제가 아니라면 모두 정답으로 허용해주는 릿코드라서 3중 반복문으로도 통과할 수 있을 것 같다.
근데 반복문이 3개 들어가면 자존심에 스크래치가 나니까 DP를 활용해보자.
거지같이 그려도 찰떡같이 알아들을 거라고 믿습니다.
이렇게 2중 배열을 만들었을 때, 행은 각 문자열, 열은 해당 문자열에서 어디까지가 팰린드롬인지를 저장한다.
한 글자도 팰린드롬이라고 했으니 [0][0], [1][1], [2][2], [3][3]은 true다.
그리고 인접한 문자열이 같을 경우 (즉, [1]과 [2]가 같을 경우)
혹은 중간의 문자열을 제외한 사이드의 문자열이 같을 경우 ( [0] [1] [2]에서 0과 2가 같을 경우 )는 모두 팰린드롬이다.
마지막으로, [1], [2], [3], [4], [5]에서 [2][4]가 true일 경우 [1]과 [5]가 같다면 [1][5]는 true다.
이를 정리하자면
boolean[][] arr[i][i] = true
boolean[][] arr[i][j] = ( j와 i의 차이가 1 혹은 2일 경우) ? s.charAt(i) == s.charAt(j)
boolean[][] arr[i][j] = ( j와 i의 차이가 2보다 클 경우) ? s.charAt(i) == s.charAt(j) == arr[i+1][j-1];
이 나온다.
이걸 그냥 코드로 옮기면 정답이다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
|
class Solution {
private int maxLength = 0;
private String answer = "";
public String longestPalindrome(String s) {
int n = s.length();
boolean[][] checked = new boolean[n][n];
for (int i=s.length()-1; i>=0; i--) {
checked[i][i] = true;
for (int j=i+1; j<n; j++) {
if (searchPalindrom(checked, i, j, s)) {
if (maxLength < j-i) {
maxLength = j-i;
answer = s.substring(i, j+1);
}
}
}
}
return (answer.length() == 0) ? s.split("")[0] : answer;
}
private boolean searchPalindrom(boolean[][] checked, int left, int right, String s) {
int l = left;
int r = right;
if (s.charAt(l) != s.charAt(r)) return false;
// 두 문자열이 같지 않을 경우 비교할 필요가 없음.
if (r-l < 3) {
return checked[l][r] = true;
}
if (r-l >= 3) {
if (checked[l+1][r-1]) return checked[l][r] = true;
}
// [2][4]가 팰린드롬일 때, [1] == [5]라면 [1][5]도 팰린드롬임.
return false;
}
}
|
cs |
반대로 i를 0부터 증가시키고 j를 i부터 0까지 감소시켜도 결과는 같다.
메서드명은 searchPalindrom이 아니라 validatePalindrom 혹은 isPalindrom이 적절했을 것 같네요.