- 동적 프로그래밍 → "메모이제이션"
- 기존 문자열과 반전된 문자열을 비교하여 똑같은 연속된 문자열 찾기
- vector<vector<int>> P[s.size() + 1][s.size() + 1]
(s[i] == s[j]) → P[i][j] = P[i-1][j+1] + 1;
- 가장 큰 P[i][j]의 값을 찾아 그 값과 i-1 을 사용하여 substr 생성 및 리턴
class Solution {
public:
string longestPalindrome(string s) {
int loc, max = 0;
vector<vector<int>> D(s.size()+1);
//LCS 변형
for(int i=0; i<D.size(); i++) {
D[i].resize(s.size()+1, 0);
for(int j=s.size(); j >= 0; j--) {
if(i==0 || j==s.size()) continue;
if(s[i-1] == s[j]) {
D[i][j] = D[i-1][j+1] + 1;
if(D[i][j] > max) {
max = D[i][j];
loc = i-1;
}
}
}
}
return s.substr(loc-max+1, max);
}
};
그냥 앞뒤로 공통된 가장 긴 문자열을 찾아내버릴뿐 palindromic하지 않는 예외가 존재한다.
"abcdbbfcba" → "bb" (output = "abc")
"aacabdkacaa" → "aca" (output = "aaca")