Longest Palindromic Substring

yyeahh·2020년 11월 14일
0

LeetCode

목록 보기
6/9

Longest Palindromic Substring

|| 문제설명 ||

  1. 문자열 s에서 가장 긴 palindromic 부분문자열을 반환하시오.
  2. s는 영어(대문자, 소문자)와 숫자로 이루어져있습니다.

|| 문제해결방법 ||

- 동적 프로그래밍 → "메모이제이션"
- 기존 문자열과 반전된 문자열을 비교하여 똑같은 연속된 문자열 찾기
- 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 생성 및 리턴


|| 코드 ||

[2020.11.14] 실패
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")

0개의 댓글