Đếm số palindromes trong một chuỗi trong python

Để triển khai phương pháp lập trình động từ dưới lên, chúng tôi xem xét hai mảng 2 chiều dp và p có kích thước n X n , trong đó n là độ dài chuỗi.
dp[i][j] lưu trữ số chuỗi con palindromic từ chỉ mục i tới j và p [i][j] giá trị boolean tùy thuộc vào việc chuỗi con từ chỉ mục i tới j là palindromic hay .

thuật toán

1. Trường hợp cơ bản là mỗi ký tự đơn lẻ là một bảng màu

2. Đối với độ dài là hai, nếu hai ký tự bằng nhau thì dp[i][i+1]=3 và p[i][i+1]=true, ngược lại nếu các ký tự khác nhau thì dp[i][i+1

3. Bây giờ chúng tôi tính toán cho các chuỗi con có độ dài cao hơn. Nếu phần đầu và phần cuối khớp nhau và phần còn lại của chuỗi con đã là màu nhạt thì chúng ta trả về 1 + số đếm từ phần còn lại và lưu kết quả này vào dp[start][end] và cũng đặt p[start][end] true.
   Nếu phần đầu và phần cuối không khớp nhau hoặc phần còn lại của chuỗi con không phải là màu nhạt thì chúng tôi trả về số đếm từ phần còn lại và lưu kết quả này vào dp[start][end] và cũng tạo p[ .

4. Cuối cùng trả về giá trị được lưu trữ trong dp[0][n-1] để lấy số chuỗi con palindromic;

Thực hiện

#include 
using namespace std;

int countPalindromicSubstrings(string str)
{

    int n = str.length();

    if (n == 0 || n == 1)
        return n;

    vector > dp(n);
    vector > p(n);

    for (int i = 0; i < n; i++) {
        dp[i] = vector(n);
        p[i] = vector(n);
    }
   

    for (int i = 0; i < n; i++) {
        dp[i][i] = 1;
        p[i][i] = true;
        if (i == n - 1)
            break;
        if (str[i] == str[i + 1]) {
            dp[i][i + 1] = 3;
            p[i][i + 1] = true;
        }
        else {
            dp[i][i + 1] = 2;
            p[i][i + 1] = false;
        }
    }
    for (int l = 3; l <= n; l++) {
        for (int start = 0; start <= n - l; start++) {
            int end = start + l - 1;
            if (str[start] == str[end] && p[start + 1][end - 1]) {
                dp[start][end] = dp[start + 1][end] + dp[start][end - 1] - dp[start + 1][end - 1] + 1;
                p[start][end] = true;
            }
            else {
                dp[start][end] = dp[start + 1][end] + dp[start][end - 1] - dp[start + 1][end - 1];
                p[start][end] = false;
            }
        }
    }
    return dp[0][n - 1];
}

int main()
{
    
    string str;

    cin >> str;

    cout << countPalindromicSubstrings(str) ;
    

    return 0;
}

Độ phức tạp về thời gian. O(n^2)

Ở đây khi chúng ta sử dụng hai mảng 2 chiều để lập trình động, do đó, không gian phụ cần có là O(n^2) và do đó,

Độ phức tạp của không gian. O(n^2)

Chúng ta cũng có thể có cách tiếp cận lập trình động từ trên xuống như được thảo luận bên dưới

Top Down DP là phiên bản ghi nhớ của phương pháp đệ quy

Để triển khai cách tiếp cận từ trên xuống, chúng tôi khởi tạo hai mảng 2D. dp[n][n] và p[n][n] trong đó n là độ dài của chuỗi

dp[i][j] lưu trữ số chuỗi con palindromic từ i đến j và p[i][j] lưu trữ 1 nếu chuỗi con từ i đến j là palindromic và 0 nếu không

thuật toán

1. Nếu i>j thì không thể có chuỗi con như vậy, do đó chúng tôi trả về 0;
2. Nếu i==j thì chỉ có một ký tự duy nhất trong chuỗi con và như chúng ta biết mọi ký tự đều là một chuỗi con đối xứng do đó chúng ta trả về 1;
3. mặt khác, chúng tôi có một chuỗi con có độ dài cao hơn từ i đến j. Chúng tôi kiểm tra xem chúng tôi đã thực hiện các tính toán cho các giá trị này của i và j chưa và nếu có thì trả về giá trị dp[i][j]
4. khác nếu không bây giờ chúng tôi kiểm tra xem chuỗi con có phải là màu nhạt hay không
5. Nếu chuỗi con từ i đến j là một chuỗi đối xứng thì chúng ta tăng số chuỗi con đối xứng lên 1 và kiểm tra các chuỗi con (i, j-1) và (i+1, j) và loại bỏ chuỗi con đối xứng chung (i+1
6. Nếu chuỗi con từ i đến j không phải là một chuỗi đối xứng thì chúng tôi kiểm tra các chuỗi con đối xứng còn lại (i, j-1) và (i+1, j) và xóa chuỗi con đối xứng phổ biến (i+1 , j-1) và lưu trữ

Ngoài ra, trong khi tìm xem chuỗi con từ i đến j có thuộc loại xuôi ngược hay không, chúng ta có một mảng 2 chiều p, trong đó p[i][j] lưu trữ kết quả nếu chuỗi con từ i đến j có thuộc dạng xuôi ngược hay không

Thực hiện

#include 
#include
using namespace std;

int p[100][100];
int dp[100][100];

bool isPalindrome(string str,int i,int j)
{  
    if (i > j)
        return 1;
    
    if (p[i][j] != -1)
        return p[i][j];
   
    if (str[i] != str[j])
        return p[i][j] = 0;
 
    return p[i][j] = isPalindrome(str, i + 1, j - 1);
}

int PalindromicSubstrings(int i, int j,string str){
   if(i>j) return 0;

   if(i==j) return 1;
   
   if(dp[i][j]!=-1) return dp[i][j];
  
   if(isPalindrome(str,i,j)) return dp[i][j]=PalindromicSubstrings(i+1,j,str)+ PalindromicSubstrings(i,j-1,str)+1-PalindromicSubstrings(i+1, j-1,str);

   else return dp[i][j]= PalindromicSubstrings(i+1,j,str)+ PalindromicSubstrings(i,j-1,str)-PalindromicSubstrings(i+1, j-1,str);
}   
int main() {

    string str;
    cin>>str;
    memset(p,-1,sizeof(p));
    memset(dp,-1,sizeof(dp));

    cout<

Như chúng ta đã thấy rằng sử dụng phương pháp lập trình động, chúng ta có độ phức tạp không gian là O(n^2). Vì vậy, bây giờ chúng ta hãy xem liệu có thể có cùng độ phức tạp thời gian nhưng độ phức tạp không gian tốt hơn bằng cách sử dụng một số thuật toán khác không

#include 
#include 
#include 
using namespace std;

set s;
int count=0;

void func(string str, int start, int end)
{
    
    while (start >= 0 && end < str.length() && str[start] == str[end])
    {
        
        count++;
 
        // Expand in both directions
        start--, end++;
    }
}
 

int countPalindromicSubstrings(string str)
{
 
    for (int i = 0; i < str.length(); i++)
    {
        // find all odd length palindrome with `str[i]` as a midpoint
        func(str, i, i);
 
        // find all even length palindrome with `str[i]` and `str[i+1]` as
        // its midpoints
        func(str, i, i + 1);
    }
 
    return count;
}
 
int main()
{
    string str ;
    cin>>str;
 
    cout<