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


Күрделілік дәрежесі орта
Жиі кіреді Amazon Facebook Google Microsoft
Кері шегіну Тереңдікті бірінші іздеу Динамикалық бағдарламалау String

Проблемалық мәлімдеме

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

мысал 

asaaaassss
2

Түсініктеме: Мұнда кіріс жолын келесідей кесуге болады asa | ааа | ssss, осылайша біз екі кесуді талап етеміз.

zxxzxxzyuy
1

Түсініктеме: Мұнда кіріс жолын келесідей кесуге болады zxxzxxz | юй, сондықтан бізге бір кесу керек.

 

Палиндромды бөлуге арналған тәсіл

Аңғал көзқарас

Ойланатын бірінші нәрсе - қарапайым рекурсивті шешім. Қарастырайық, бізде 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 коды

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 - кез-келген палиндромдық ішкі жолдың оң шекарасы), біз кесінділерді бір өлшемді массив ретінде сақтаймыз, бұл ішкі тізбектің басталуына қажетті минималды санын сақтаймыз. 0-ден i-ге дейін. Ішкі цикл j-ден 0-ден i-1-ге дейін жүреді, біз [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 коды

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) алдық.

, O (N ^ 2) кесінділердің минималды санын табуға арналған. Сыртқы цикл жолдың барлық ұзындығынан, ал ішкі цикл 0-ден i-1-ге дейін жүретіндіктен.

Осылайша, жұмыс уақытын барлығы O (N ^ 2) құрайды.

Ғарыштың күрделілігі: O (N ^ 2)

Біздің кесінділер массиві қазір бір өлшемді болса да, біздің isPalindrome әлі де 2D массив болып табылады.