[LeetCode] 5. Longest Palindromic Substring 최장 메모 하위 문자열

본 문제에서 주어진 문자열의 가장 긴 회문 문자열을 구하려면 먼저 폭력을 사용하는 방법을 생각해 볼 수 있다. 주어진 문자열의 모든 회문 문자열의 길이를 구하고 가장 긴 회문 문자열을 취하며 구체적으로 회문 문자열의 길이는 홀수와 짝수로 나누어 토론하고 시간 복잡도 O(n^2)를 구할 수 있다. 그러나 이 폭력 구해 방법은leetcode에 시간 초과 오류를 보고한다. 구체적인 코드는 다음과 같다.
하나.폭력법
참조 코드

#include<string>
#include<string.h>
using namespace std;
class Solution {
public:
    string longestPalindrome(string s) {
       if(s.empty()||s.size()<=1) return s;
       int size = s.size();
       string odd_str = longestPalindrome_odd(s,size);
       string even_str = longestPalindrome_even(s,size); 
       return odd_str.size() >= even_str.size()?odd_str:even_str;
    }
    
    string longestPalindrome_odd(string& s,int size)
    {
       string res;
       for(int i = 0; ii){
           string substr =  s.substr(i,1);
           for(int l = i-1,r = i+1;l>=0 && r<=size-1;l--,r++){
                if(s[l]!=s[r]) break;
                 else{
                   substr = s.substr(l,r-l+1);
                }
           }
           if(substr.size()>=res.size()) res = substr;
       }
       return res;
    }

    string longestPalindrome_even(string& s,int size)
    {
        string res; 
        for(int i = 0; ii){
            string substr;
            for(int l = i,r = i+1;l>=0&&r<=size-1;l--,r++){
                if(s[l]!=s[r]) break;
                else{
                  substr = s.substr(l,r-l+1);
                }
            }
            if(substr.size()>=res.size()) res = substr;
        }
        return res;
    }
};

 
2 동적 계획:
1단계: 상태 dp[i][j]를 정의하면 하위 문자열s[i, j]가 회문 하위 문자열인지 여부를 나타낸다.상태를 정의하려면 먼저'제목이 물어보는 대로 상태를 설정해 보세요'.그리고'상태가 어떻게 이동하는가'를 고려한다. 만약에'상태 이동 방정식'이 쉽게 얻을 수 없다면 상태 정의를 수정하려고 시도한다. 그 목적은'상태 이동 방정식'을 쉽게 얻기 위해서이다.
 
2단계: 사고 상태 이동 방정식
이 단계에서는 상태 정의에 대한 분석에 따라 머리와 꼬리 문자가 동일한지 여부에 따라 분류 토론을 수행합니다.
dp[i][j]=(s[i]==s[j]) and dp[i+1][j-1] 이 상태 이동 방정식을 분석하려면 다음과 같이 하십시오.
(1)'동적 기획'은 사실상 2차원 표를 작성하는 것이고 i와 j의 관계는 i<=j이기 때문에 이 표의 상반부만 작성해야 한다.
(2) s[i]=s[j]의 성립과 j-i<3의 전제에서 직접 결론을 내릴 수 있다. dp[i][j]=true, 그렇지 않으면 상태 이동을 실행할 수 있다.
주: 분류 토론은 전태 전이 방정식을 구성하는 기교이다.상태 공간을 분류하고 최우수자 구조가 도대체 무엇인지 생각한다.즉 큰 문제의 최우선을 어떻게 작은 문제의 최우선으로 풀 수 있느냐는 것이다.
 
3단계: 초기화 고려
초기화할 때 단일 문자는 반드시 회문열이어야 하기 때문에 대각선을 먼저 1, 즉 dp[i][i]=1로 초기화한다.
사실상 초기화된 부분은 모두 생략할 수 있다.문자가 하나일 때 반드시 답장이 있기 때문에 dp[i][i]는 다른 상태 값에 참고되지 않습니다.
4단계: 출력을 고려할 때 dp[i][j]=true를 얻으면 하위 문자열의 길이와 시작 위치를 기록한다. 캡처할 필요가 없다. 캡처 문자열도 성능을 소모하기 때문에 이때의 하위 문자열의'시작 위치'와'메시지 길이'를 기록하면 된다.
5단계: 상태를 압축할 수 있는지 고려한다. 왜냐하면 표를 작성하는 과정에서 왼쪽 아래의 수치만 참고했기 때문이다.사실상 압축할 수 있지만 판단 문장을 늘리고 코드 작성과 이해의 난이도를 높여 가독성을 잃게 된다.여기서는 상태 압축을 하지 않는다.
다음은 인코딩할 때 주의해야 할 사항이다. 항상 먼저 작은 문자열의 회문 판정을 받은 다음에 큰 문자열이 작은 문자열의 판단 결과를 참고할 수 있다.
아이디어는 다음과 같습니다.
1. 서브열 오른쪽 경계 j가 점차적으로 확대되는 과정에서 왼쪽 경계가 나타날 수 있는 위치를 매거한다.
2. 왼쪽 경계를 매거할 때 작은 것부터 큰 것까지, 큰 것부터 작은 것까지 매거할 수 있다.
참조 코드 2:

class Solution {
public:
    string longestPalindrome(string s) {
        const int size = s.size();
        if(s.empty()||size <= 1)
           return s;
        int l=0,h=0,seq=0;
       bool dp[size][size];
        for(int j = 1;jj)
           for(int i = 0;i<=j;++i)
            {
                int sub_seq = j-i+1;
                if(sub_seq<3)
                {
                    dp[i][j]=s[i]==s[j];
                }
                else
                {
                     dp[i][j]=(s[i]==s[j]&&dp[i+1][j-1]);
                }
                if(dp[i][j]&&sub_seq>=seq){
                    l=i;
                    h=j;
                    seq=sub_seq;
                }
            }
            return s.substr(l,seq);
    }
};