가장 긴 Palindromic Subsequence


난이도 중급
자주 묻는 질문 아마존 페이스북 서비스 Microsoft
동적 프로그래밍

가장 긴 회문 하위 시퀀스 문제에서 우리는 , 가장 긴 회문 하위 시퀀스의 길이를 찾으십시오.

입력:
튜토리얼 컵
출력:
3

입력:
동적 프로그래밍
출력:
7

가장 긴 Palindromic Subsequence

가장 긴 Palindromic Subsequence에 대한 순진한 접근 방식

위의 문제를 해결하기위한 순진한 접근 방식은 주어진 문자열의 모든 하위 시퀀스를 생성하고 가장 긴 회문 하위 시퀀스의 길이를 찾는 것입니다.
시간 복잡성은 기하 급수적 인, 매우 높습니다.

가장 긴 Palindromic Subsequence를위한 최적의 접근법

위의 문제는 최적의 하부 구조와 겹치는 특성을 가지고 있으므로 동적 프로그래밍 문제를 해결하는 데 사용할 수 있습니다.
주어진 문자열의 길이를 n으로하고 s에 대한 가장 긴 회문 하위 시퀀스 길이를 LPS (s, 0, n – 1)로 표시합니다.
s –> 주어진 문자열
0 –> 시작 색인
n – 1 –> 끝 인덱스

  • s (주어진 문자열)의 첫 번째와 마지막 문자가 같으면,
    LPS (s, 0, n – 1) = 2 + LPS (s, 1, n – 2)
  • 그밖에,
    LPS (s, 0, n – 1) = 최대 (LPS (s, 0, n – 2), LPS (s, 1, n – 1))
  • 기본 케이스 : 길이가 1 인 문자열은 항상 회문입니다. 즉, LPS (s, i, i) = 1
  • 기본 케이스 : 문자열에 두 개의 문자가 있고 둘 다 같으면 회문입니다.

이 재귀 및 메모를 사용하여 LPS를 더 나은 시간 복잡성으로 찾을 수 있습니다.

암호알고리즘

  1. 크기 (n X n)의 2 차원 배열 lps를 만듭니다. 여기서 n은 문자열 s의 길이이며 x에서 y까지 시작하는 가장 긴 회문 하위 시퀀스의 길이를 저장합니다. 여기서 x는 행 번호이고 y는 열 번호입니다. 위의 문제에 대한 답은 LPS [0] [n – 1]입니다.
  2. 문자열 s, 시작 인덱스 i 및 종료 인덱스 e가 제공됩니다.
  3. i와 e가 같으면 1 (Base Case)을 반환합니다.
  4. i + 1 = e이고 s의 i와 e에있는 문자가 같으면 2 (Base Case)를 반환합니다.
  5. 그렇지 않으면 문자열 s의 위치 i와 e에있는 문자가 같으면 2 + LPS (s, i + 1, e – 1)를 반환합니다.
  6. Else return max (LPS (s, i + 1, e), LPS (s, i, e – 1)).
  7. 재귀 호출을하기 전에 lps 배열의 해당 값을 확인하십시오. 즉, LPS (s, i, e)가 lps [i] [e]에 있는지 확인하십시오. lps 배열에 값이 없으면 재귀 호출을 수행하십시오. else 계산 된 값을 사용하십시오. 이 단계는 알고리즘의 시간 복잡성을 줄이는 역할을합니다.

시간 복잡성 = O (n ^ 2)

가장 긴 Palindromic Subsequence를위한 JAVA 코드

public class LongestPalindromicSubsequence {

    // Function to return the length of longest palindromic subsequence
    private static int LPS(String s) {
        int n = s.length();
        int[][] lps = new int[n][n];

        return lpsUtil(s.toCharArray(), 0, n - 1, lps);
    }

    // Recursive utility function to calculate the length of longest palindromic subsequence
    private static int lpsUtil(char[] s, int i, int e, int[][] lps) {
        // Return if already calculated
        if (lps[i][e] != 0) {
            return lps[i][e];
        }

        // Base case (String of length 1 is always a palindrome)
        if (i == e) {
            lps[i][e] = 1;
            return 1;
        }

        // Base Case (If there are only 2 characters and both are same)
        if (s[i] == s[e] && i + 1 == e) {
            lps[i][e] = 2;
            return 2;
        }

        // If first and last characters are same then
        // LPS(s, i, e) = 2 + LPS(s, i + 1, e - 1)
        if (s[i] == s[e]) {
            // If not calculated before, find the result and store in lps array
            if (lps[i + 1][e - 1] == 0) {
                lps[i + 1][e - 1] = lpsUtil(s, i + 1, e - 1, lps);
            }

            // Store the result in lps array
            lps[i][e] = 2 + lps[i + 1][e - 1];
            return lps[i][e];
        } else {
            // If not calculated before, find the result and store in lps array
            if (lps[i + 1][e] == 0) {
                lps[i + 1][e] = lpsUtil(s, i + 1, e, lps);
            }
            // If not calculated before, find the result and store in lps array
            if (lps[i][e - 1] == 0) {
                lps[i][e - 1] = lpsUtil(s, i, e - 1, lps);
            }

            // Store the result in lps array
            lps[i][e] = Math.max(lps[i + 1][e], lps[i][e - 1]);
            return lps[i][e];
        }
    }

    public static void main(String[] args) {
        // Example 1
        System.out.println(LPS("TUTORIALCUP"));

        // Example 2
        System.out.println(LPS("DYNAMICPROGRAMMING"));
    }
}

가장 긴 Palindromic Subsequence를위한 C ++ 코드

#include <bits/stdc++.h>
#define MAXN 1000
using namespace std;

// Global array to store the lps for a given string
int lps[MAXN][MAXN];

// Recursive utility function to calculate the length of longest palindromic subsequence
int lpsUtil(string s, int i, int e) {
    // Return if already calculated
    if (lps[i][e] != 0) {
        return lps[i][e];
    }
    
    // Base case (String of length 1 is always a palindrome)
    if (i == e) {
        lps[i][e] = 1;
        return 1;
    }
    
    // Base Case (If there are only 2 characters and both are same)
    if (s[i] == s[e] && i + 1 == e) {
        lps[i][e] = 2;
        return 2;
    }
    
    // If first and last characters are same then
    // LPS(s, i, e) = 2 + LPS(s, i + 1, e - 1)
    if (s[i] == s[e]) {
        // If not calculated before, find the result and store in lps array
        if (lps[i + 1][e - 1] == 0) {
            lps[i + 1][e - 1] = lpsUtil(s, i + 1, e - 1);
        }
        
        // Store the result in lps array
        lps[i][e] = 2 + lps[i + 1][e - 1];
        return lps[i][e];
    } else {
        // If not calculated before, find the result and store in lps array
        if (lps[i + 1][e] == 0) {
            lps[i + 1][e] = lpsUtil(s, i + 1, e);
        }
        // If not calculated before, find the result and store in lps array
        if (lps[i][e - 1] == 0) {
            lps[i][e - 1] = lpsUtil(s, i, e - 1);
        }

        // Store the result in lps array
        lps[i][e] = std::max(lps[i + 1][e], lps[i][e - 1]);
        return lps[i][e];
    }
}

// Function to return the length of longest palindromic subsequence
int LPS(string s) {
    int n = s.length();
    
    // Initialise lps as 0
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            lps[i][j] = 0;
        }
    }
    
    return lpsUtil(s, 0, n - 1);
}

int main() {
    // Example 1
    cout<<LPS("TUTORIALCUP")<<endl;
    
    // Example 2
    cout<<LPS("DYNAMICPROGRAMMING")<<endl;
    
    return 0;
}
3
7

참조