[Programmers] 가장 긴 팰린드롬

*O(n^2)로 해결 O(n)으로 하는 방법은 없을까..?

*dp를 이용해서 i는 시작점 / j는 도착점으로 간주해서 팰린드롬이면 dp[i][j] = true 로 저장한다. 

*자기 자신은 항상 팰린드롬 

aa, bb -> 길이가 2인 팰린드롬 

 

*for (len => 비교할 길이)

    for (시작점-> n-len) 

      int j = 도착점

       if (s[i] == s[j] && dp[i+1][j-1] : 범위를 좁혀가면서 팰린드롬인지 확인) 

         dp[i][j] = true;

         answer의 최대값을 비교한다.  

 

#include <iostream> #include <string> using namespace std; bool dp[2500][2500]; int solution(string s) { int answer=1; // [실행] 버튼을 누르면 출력 값을 볼 수 있습니다. int n = s.size(); for (int i = 0; i < n; i++ ) dp[i][i] = true; //자기 자신은 항상 팰린드롬 for (int i = 0; i < n-1; i++) { if (s[i] == s[i+1]) { answer = 2; dp[i][i+1] = true; //중앙이 없는 2개씩끊어서 확인함 } } for (int len = 2; len < n; len++) { for (int i = 0; i <= n-len; i++) { int j = i + len; if (s[i] == s[j] && dp[i+1][j-1]) { dp[i][j] = true; answer = answer > j-i+1 ? answer : j-i+1; } } } return answer; }