Palindrom Bölmə

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

Problem bəyanat

Bir simli nəzərə alaraq, arakəsmlərin bütün alt telləri palindromlar olması üçün tələb olunan minimum kəsik sayını tapın. Orijinal simlərimizi bütün alt tellərin palindrom olması üçün fərqli arakəsmələrə ayırdığımız üçün bu problemi Palindrom Bölmə Problemi adlandırırıq.

misal 

asaaaassss
2

İzahat: Burada giriş simli kimi kəsə bilərik asa | aaa | ssss, beləliklə iki kəsik tələb edirik.

zxxzxxzyuy
1

İzahat: Burada giriş simli kimi kəsə bilərik zxxzxxz | yuy, buna görə tək bir kəsik lazımdır.

 

Palindrom Bölmə üçün yanaşma

Sadəlövh yanaşma

Ağla gələn ilk şey sadə bir rekursiv həlldir. N uzunluğunda bir tel var deyək. Sətir palindromdursa, sadəcə 0 cavabını qaytara bilərik, ancaq palindrom deyilsə. Bütün imkanları sınayırıq, demək istədiyim budur ki, kth indeksindəki iki hissədə ipi kəsib sonra sol və sağ hissə üçün ayrı-ayrılıqda həll edək. Bu həll tamamilə düzgündür, lakin səmərəli deyil.

minCut(string s, int i, int j) = 1 + min( minCut(s, i, k) + minCut(s, k+1, j) )

where k ranges from i to j

i, j, k are indices on string

Palindrom BölməPin

Səmərəli yanaşma

İndiyə qədər araya bir kəsik qoyarkən ipin sol hissəsini və sağ hissəsini həll edən sadə bir həll yolu bilirik. Beləliklə, əvvəlcə n ölçülü bir sətirdə bir problem yaşadıq və sonra problemimizi iki alt problemə endirdik deyə bilərik. Alt problemlərin quruluşunu görsək, şübhəsiz ki, üst-üstə düşürlər. Beləliklə, bu istifadə edilməsini təklif edir Dinamik proqramlaşdırma əvvəlki həllin eksponensial zaman mürəkkəbliyini azaltmaq üçün O (N ^ 3). Şəkildə üst-üstə düşən alt problemlər qırmızı rəngdə göstərilir. Bənzər Dinamik proqramlaşdırma naxış görülə bilər Matris Zəncirinin Çarpılması Problemi, əvvəlcə daha kiçik alt problemləri həll etdikdən sonra nəticələrini orijinal problemin həlli üçün birləşdiririk.

Palindrom Bölmə Kodu

C ++ kodu

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

int minCut(string s) {
    int n = s.length();
    vector<vector<int>> cuts;
    vector<vector<bool>> isPalindrome;
    cuts.assign(n,vector<int>(n, INT_MAX));
    isPalindrome.assign(n, vector<bool>(n, false));
    
    for(int len = 1;len<=n;len++) {
        for(int i=0;i<n-len+1;i++) {
            int j = i+len-1;
            if(len <= 2)
                isPalindrome[i][j] = s[i] == s[j];
            else
                isPalindrome[i][j] = s[i] == s[j] && isPalindrome[i+1][j-1];
            
            if(isPalindrome[i][j]) {
                cuts[i][j] = 0;
            } else {
                for(int k=i;k<j;k++)
                    cuts[i][j] = min(cuts[i][j], 1+cuts[i][k]+cuts[k+1][j]);
            }
        }
    }
    return cuts[0][n-1];
}

int main() {
  int t;cin>>t;
  while(t--){
      string s;
      cin>>s;
      cout<<minCut(s)<<endl;
  }
}

Java kodu

import java.util.*;
import java.lang.*;
import java.io.*;

class Main {
    public static int minCut(String s) {
        int n = s.length();
        int cuts[][] = new int[n][n];
        boolean isPalindrome[][] = new boolean[n][n];
        
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                cuts[i][j] = Integer.MAX_VALUE;
            }
        }
        
        for(int len = 1;len<=n;len++) {
            for(int i=0;i<n-len+1;i++) {
                int j = i+len-1;
                if(len <= 2)
                    isPalindrome[i][j] = s.charAt(i) == s.charAt(j);
                else
                    isPalindrome[i][j] = s.charAt(i) == s.charAt(j) && isPalindrome[i+1][j-1];
                
                if(isPalindrome[i][j]) {
                    cuts[i][j] = 0;
                } else {
                    for(int k=i;k<j;k++)
                        cuts[i][j] = Math.min(cuts[i][j], 1+cuts[i][k]+cuts[k+1][j]);
                }
            }
        }
        return cuts[0][n-1];    
    }
    
  public static void main (String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    int t = Integer.parseInt(br.readLine());
    while(t-- > 0) {
        String s = br.readLine();
        int ans = minCut(s);
        System.out.println(ans);
    }
  }
}

Zamanın mürəkkəbliyi: O (N ^ 3)

İlk döngə 1-dən n-ə qədər (len = 1-len = n)

Alt problem (i) üçün başlanğıc indeksini ifadə edən iç içə döngü 0-dan n-len-ə qədər işləyir

K ilə k + 1 arasındakı kəsik indeksini ifadə edən ən daxili döngə də i-dən j-ə qədər uzanır. 

Beləliklə, ən pis halda, zamanın mürəkkəbliyinin O (N ^ 3) olduğu deyilir.

Kosmik Mürəkkəblik: O (N ^ 2)

İki ölçülü massiv olan isPalindrome və kəsiklər var və beləliklə O (N ^ 2) kosmik mürəkkəbliyə sahibik.

 

Palindrom Bölmə üçün Optimize Çözüm

Zamanın mürəkkəbliyini daha da azalda bilərik O (N ^ 2), isPalindrome matrisini əvvəlcədən hesablamaqla. Sonra i-dən j-yə qədər alt sətir üçün kəsiklər saxlamaq yerinə (burada i sərhəddir və j hər hansı bir palindrom alt sətrin sağ sərhədidir), kəsikləri başlanğıc üçün lazım olan minimum sətir sayını saxlayan tək ölçülü bir sıra kimi saxlayırıq. 0-dan i. Daxili döngə 0-dan i-1-ə qədər j üzərində işləyir, burada [j, i] alt sətirinin palindrom olub olmadığını yoxlayırıq? Substring palindromdursa, [j, i] alt sətri [0, j-1] + 1 ilə eyni sayda kəsiklərə sahibdir. Beləliklə, yalnız j-dən olan bütün variantların minimumunu saxlayaraq cavabı yeniləyirik. 0-dan i-1-ə. Beləliklə, nəticədə, bütün bölmələrin palindrom olması üçün tələb olunan minimum kəsmə sayımız var.

C ++ kodu

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

int minCut(string s) {
    int n = s.length();
    vector<int> cuts;
    vector<vector<bool>> isPalindrome;
    cuts.assign(n,INT_MAX);
    isPalindrome.assign(n, vector<bool>(n, false));
    
    for(int len = 1;len<=n;len++) {
        for(int i=0;i<n-len+1;i++) {
            int j = i+len-1;
            if(len <= 2)
                isPalindrome[i][j] = s[i] == s[j];
            else
                isPalindrome[i][j] = s[i] == s[j] && isPalindrome[i+1][j-1];
        }
    }
    
    cuts[0] = 0;
    for(int i=1;i<n;i++) {
        for(int j=1;j<=i;j++)
            if(isPalindrome[0][i])
                cuts[i] = 0;
            else if(isPalindrome[j][i])
                cuts[i] = min(cuts[i], 1 + cuts[j-1]);
    }
    return cuts[n-1];
}

int main() {
  int t;cin>>t;
  while(t--){
      string s;
      cin>>s;
      cout<<minCut(s)<<endl;
  }
}

Java kodu

import java.util.*;
import java.lang.*;
import java.io.*;

class Main {
    public static int minCut(String s) {
        int n = s.length();
        int cuts[] = new int[n];
        boolean isPalindrome[][] = new boolean[n][n];
        
        for(int i=0;i<n;i++) {
            cuts[i] = Integer.MAX_VALUE;
        }
        
        for(int len = 1;len<=n;len++) {
            for(int i=0;i<n-len+1;i++) {
                int j = i+len-1;
                if(len <= 2)
                    isPalindrome[i][j] = s.charAt(i) == s.charAt(j);
                else
                    isPalindrome[i][j] = s.charAt(i) == s.charAt(j) && isPalindrome[i+1][j-1];
            }
        }
        
        cuts[0] = 0;
        for(int i=1;i<n;i++) {
            for(int j=1;j<=i;j++)
                if(isPalindrome[0][i])
                    cuts[i] = 0;
                else if(isPalindrome[j][i])
                    cuts[i] = Math.min(cuts[i], 1 + cuts[j-1]);
        }
        return cuts[n-1];
    }
    
  public static void main (String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    int t = Integer.parseInt(br.readLine());
    while(t-- > 0) {
        String s = br.readLine();
        int ans = minCut(s);
        System.out.println(ans);
    }
  }
}

Zamanın mürəkkəbliyi: O (N ^ 2)

İndeksdən j-yə qədər alt sətrin palindrom olub olmadığını saxlamaq üçün O (N ^ 2) götürdük.

Minimum kəsik sayını tapmaq üçün O (N ^ 2). Xarici döngə ipin bütün uzunluğu boyunca və daxili döngə 0-dan i-1-ə qədər olduğundan.

Beləliklə, iş müddətini ümumi O (N ^ 2) halına gətirmək.

Kosmik Mürəkkəblik: O (N ^ 2)

Artıq kəsiklərimiz tək ölçülü olsa da, isPalindromumuz hələ də 2 ölçülü bir massivdir.

Translate »