Palindrom Bölmə

Çətinlik səviyyəsi Mühit
Tez-tez soruşulur Amazon Facebook google
Geri qayıtma Dərinlik İlk Axtarış Dinamik proqramlaşdırmaBaxılıb 33

Palindrom Bölmə birdir DP problemi. Bu problemdə, bölmənin hər alt sətirinin palindrom olması üçün S. bölməsi verilmişdir. S-nin palindromla bölünməsi üçün lazım olan minimum kəsikləri yazdırmalıyıq.

Giriş Formatı

Yalnız S sətri olan bir sətir.

Çıxış formatı

S-nin palindromlu bölüşdürülməsi üçün lazım olan minimum kəsik olan tək tam ədədi çap edin.

Məhdudiyyətlər

  • 1 <= | s | <= 1000.
Example Input:
abcdefedc
Example Output:
2

Palindrom Bölmə üçün İzahat

Burada 3 kəsikdən istifadə edərək ipi 2 alt telə böldük. Substrings "a", "b", "cdefedc" dir. Burada bir alt sətrin palindrom olub olmadığını izah edən məlumatların saxlanması üçün 2B matrisdən istifadə edirik. DP [i] [j] 1-dirsə, s (i, j) alt sətri başqa bir palindromdur DP [i] [j] = 0 deməkdir. İndi minimum kəsilmələrin sayı üçün əvvəlki kəsim haqqında məlumatları [0-i] -dən saxlayan bir sıra lazımdır.

DP [0] [1] 1-dirsə, [i] = 0-ı başqa şəkildə kəsir, j + 1-dən i-yə alt sətrin palindrom olduğunu və [j] +1 kəsiklərinin minimum 0 <= j olduğu mümkün olduğunu yoxlayın.

Bundan sonra istirahət alt telləri üçün tapdığımız minimum kəsiklərdən istifadə edərək minimum kəsikləri 0-dan i-yə qədər yeniləməyimiz lazımdır.

Palindrom Bölmə üçün Alqoritm

Algorithm:
Step:1 Set dp[n][n]=0.
Step:2 Set dp[i][i]=1 for all i where 0<=i<n.This is for all substrings of length 1 are palindrome.
Step:3 For all values of i where 0<=i<n-1, we check if s[i]=s[i+1] then dp[i][i+1]=1. This is for all substrings of length 2 are palindrome. 
Step:4 For rest of the other length substring:
        for i in range 3 to n:
            for j in range 0 to n-i:
                last=j+i-1.
                if s[j]=s[last] then:
                   if dp[j+1][last-1] then:
                      dp[j][last]=1;
Step:5 Count the minimum cuts required. Make a array cuts of size n and set all its value as 1e9.
       for i in range 0 to n-1:
            set calc as 1e9.
            if dp[0][i] is 1 then:
                cuts[i]=0;
            else:
                for j in range 0 to i-1:
                    if dp[j+1][i]=1 and calc greater than (cuts[j]+1) then:
                        set calc=cuts[j]+1.
                set cuts[i]=calc;
Step:6 Print the value of cuts[n-1].

Palindrom Bölmə üçün tətbiqetmə

/*C++ Implementation of Palindrome Partitioning using DP approch*/ 
#include<bits/stdc++.h>
using namespace std;
int main() 
{ 
    /*input string*/
    string s;
    cin>>s;
    int n=s.length();
    int dp[n+1][n+1];
    /*set 0 to all cell of dp matrix.*/
    memset(dp,0,sizeof(dp));
    /*for all 1 length substrings which are palindrome.*/
    for(int i=0;i<n;i++)
    {
        dp[i][i]=1;
    }
    /*for all 2 length substrings which are palindrome.*/
    for(int i=0;i<n-1;i++)
    {
        if(s[i]==s[i+1])
        {
            dp[i][i+1]=1;
        }
    }
    /*for all substrings greater than length 2 which are palindrome.*/
    for(int i=3;i<=n;i++)
    {
        for(int j=0;j<n-i+1;j++)
        {
            int last=j+i-1;
            /*first and last char must be the same.*/
            if(s[j]==s[last])
            {
                /*substring s[i+1 to j-1] must be palindrome.*/
                if(dp[j+1][last-1]) 
                {
                    dp[j][last]=1;
                }
            }
        }
    }
    int cuts[n];
    /*set maximum value(1e9) to each cell of cuts array*/
    memset(cuts,1e9,sizeof(cuts));
    /*calculating minimum cuts*/
    for(int i=0;i<n;i++)
    {
        int calc=1e9;
        /*if substring from 0 to i is palindrome*/
        if(dp[0][i])
        {
            cuts[i]=0;
        }
        else/*others casec*/
        {
            /*check for all index less than i to get the minimum cuts for j to i*/
            for(int j=0;j<i;j++)
            {
                /*if substring from j+1 to i is a palindrome */
                if((dp[j+1][i])&&calc>cuts[j]+1)
                {
                    calc=cuts[j]+1;
                }
            }
            cuts[i]=calc;
        }
    }
    /*print the minimum cut required value*/
    cout<<cuts[n-1]<<endl;
    return 0; 
}
ssadafudedufadddd
3

Zamanın mürəkkəbliyi

O (N * N) burada N simli uzunluqdur. Dp matrisindəki dəyərləri yenilədikdə istifadə etdiyimiz döngü üçün iç içə yerləşdiyi bütün mümkün cütlükləri ziyarət etməliyik.

Kosmik Mürəkkəblik

O (N * N) burada N simli uzunluqdur. Bir alt sətrin palindrom olub olmadığını yoxlamaq üçün 2 dəyərlərini saxlamaq üçün N * N sıralı 0,1d DP matrisini yaradırıq.

References

Translate »