Палиндромду бөлүү


Кыйынчылык деңгээли орто
Көп суралган Amazon Facebook Гугл Microsoft
Backtracking Тереңдик Биринчи издөө Динамикалык программалоо аркан

Маселени билдирүү

Жипти эске алып, бөлүктөрдүн бардык подстроолору палиндромдор болгондой кылып, минималдуу кесилгендердин санын табыңыз. Баштапкы сабыбызды ар кандай бөлүктөргө бөлүп жаткандыктан, бардык подстриндер палиндромдор болгондуктан, биз бул маселени Палиндромдун Бөлүм Маселеси деп атайбыз.

мисал 

asaaaassss
2

Түшүндүрмө: Бул жерде, биз киргизилген сапты катары кесүүгө болот asa | aaa | ssss, Ошентип, биз эки кыскартууну талап кылабыз.

zxxzxxzyuy
1

Түшүндүрмө: Бул жерде, биз киргизилген сапты катары кесүүгө болот zxxzxxz | yuy, ошондуктан бизге бир жолу кесүү керек.

 

Палиндромду бөлүү ыкмасы

Naive Appocach

Акылга биринчи келе турган нерсе - бул жөнөкөй рекурсивдик чечим. Карап көрүңүз, бизде n деген узундугу бар сап бар. Эми, эгер палиндром болсо, биз жөн гана 0 деген жоопту кайтара алабыз, бирок ал палиндром болбосо. Биз бардык мүмкүнчүлүктөрдү колдонуп жатабыз, демек, мен жипти kth индекси боюнча эки бөлүккө бөлүп, андан кийин сол жана оң бөлүктөр үчүн рекурсивдүү чечүүгө аракет кылабыз. Бул чечим таптакыр туура, бирок натыйжалуу эмес.

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

Палиндромду бөлүү

Натыйжалуу мамиле

Ушул кезге чейин жиптин сол бөлүгүн жана оң бөлүгүн алардын ортосуна кесип коюп, чечүүчү жөнөкөй чечимди билебиз. Ошентип, башында n өлчөмүндөгү сап менен көйгөй келип чыкты, андан кийин эки подпроблемага кыскардык деп айта алабыз. Эгерде субпроблемалардын түзүмүн көрө турган болсок, анда алардын бири-бирине дал келиши шексиз. Демек, бул колдонууну сунуш кылат Динамикалык программалоо чейин эритменин экспоненциалдуу убакыт татаалдыгын азайтуу O (N ^ 3). Сүрөттө кызыл түстө бири-бирине дал келген субпроблемалар көрсөтүлгөн. Окшош Динамикалык программалоо үлгүсүн көрүүгө болот Матрица чынжырын көбөйтүү маселеси, анда алгач чакан чакан көйгөйлөрдү чечип, андан соң баштапкы маселени чечүү үчүн алардын натыйжаларын бириктиребиз.

Палиндромду бөлүү коду

C ++ коду

#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 Code

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);
    }
  }
}

Убакыттын татаалдыгы: O (N ^ 3)

Биринчи цикл 1ден nге чейин созулат (len = 1 ден len = n)

(I) субпроблемасы үчүн старттык индексин билдирген уюлдук цикл 0дон n-lenге чейин созулат

K менен k + 1дин ортосундагы кесүү индексин билдирген эң ички цикл дагы i ден j ге чейин созулат. 

Ошентип, эң начар учурда, убакыттын татаалдыгы O (N ^ 3) деп айтылат.

Космостун татаалдыгы: O (N ^ 2)

Бизде эки массив isPalindrome жана кесилиштер бар, алар 2D массивдер, ошондуктан бизде O (N ^ 2) мейкиндиги татаал.

 

Палиндромду бөлүү үчүн оптимизацияланган чечим

Убакыттын татаалдыгын дагы азайта алабыз O (N ^ 2), isPalindrome матрицасын алдын-ала эсептөө менен. Андан кийин i-ден j-ге чейин подстрожка үчүн кесиндилерди сактоонун ордуна (мында i сол чеги жана j - бул палиндромдук подстриндин оң чеги), биз кесимдерди бир өлчөмдүү массив катарында баштап, подстринка баштоо үчүн талап кылынган минималдуу санын сактоо менен сактайбыз. 0дөн iге чейин. Ички цикл 0 ден i-1 ге чейин j боюнча иштейт, анда [j, i] подстрин палиндромдук экендигин текшеребиз? Эгерде субстрин палиндромдук болсо, анда [j, i] подстринги [0, j-1] + 1. сыяктуу эле кесилгендердин санына ээ болот. Ошентип, биз жөн гана j бардык варианттарынын минимумун сактоо менен жообун жаңыртабыз. 0дөн i-1ге чейин. Ошентип, акыр аягында, бизде баардык бөлүктөр палиндромдор болушу үчүн, минималдуу кыскартуулар талап кылынат.

C ++ коду

#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 Code

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);
    }
  }
}

Убакыт татаалдыгы: O (N ^ 2)

Эгерде индекстен j-ге чейинки субстрин палиндром болсо, анда биз сактоо үчүн O (N ^ 2) алдык.

The, O (N ^ 2) минималдуу кыскартууларды табуу үчүн. Сырткы жиптин узундугу жана ички цикл 0ден i-1ге чейин созулгандыктан.

Ошентип, иштөө убактысын жалпы O (N ^ 2) түзөт.

Космостун татаалдыгы: O (N ^ 2)

Азыр биздин кесүү массиви бир өлчөмдүү болсо дагы, биздин isPalindrome дагы 2D массив болуп саналат.