Паліндромны перагародка


Узровень складанасці серада
Часта пытаюцца ў амазонка facebook Google Microsoft
Фанаграмы Глыбіня Першы пошук Дынамічнае праграмаванне Радок

Пастаноўка праблемы

Улічваючы радок, знайдзіце мінімальную колькасць разрэзаў, неабходных для таго, каб усе падрадкі перагародак былі паліндромамі. Паколькі мы разразаем зыходную радок на розныя раздзелы так, каб усе падрадкі былі паліндромамі, мы называем гэтую праблему праблемай падзелу паліндрома.

Прыклад 

asaaaassss
2

Тлумачэнне: Тут мы можам выразаць уваходны радок як аса | ааа | ssss, такім чынам, нам патрабуецца два разрэзы.

zxxzxxzyuy
1

Тлумачэнне: Тут мы можам выразаць уваходны радок як zxxzxxz | юй, таму нам патрэбен адзін разрэз.

 

Падыход да раздзелу паліндрома

Наіўны падыход

Першае, што прыходзіць у галаву, - простае рэкурсіўнае рашэнне. Улічыце, у нас ёсць радок даўжынёй скажам n. Цяпер, калі радок паліндром, мы можам проста вярнуць адказ 0, але калі гэта не паліндром. Мы спрабуем усе магчымасці, маючы на ​​ўвазе тое, што мы маем на ўвазе, што мы спрабуем разрэзаць радок на два раздзелы з k-м індэксам, а потым вырашаем рэкурсіўна для левай і правай часткі асобна. Гэта рашэнне абсалютна правільнае, але неэфектыўнае.

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 - левая мяжа, а j - правая мяжа любой паліндромнай падрадкі), мы захоўваем выразы ў выглядзе аднамернага масіва, які захоўвае мінімальную колькасць разрэзаў, неабходных для пачатку падрадка ад 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)

Мы ўзялі O (N ^ 2) для захоўвання, калі падрадок з індэкса да j - паліндром.

, O (N ^ 2) для пошуку мінімальнай колькасці парэзаў. Паколькі знешні цыкл праходзіць па ўсёй даўжыні радка, а ўнутраны - ад 0 да i-1.

Такім чынам, агульны час выканання O (N ^ 2).

Касмічная складанасць: O (N ^ 2)

Нягледзячы на ​​тое, што наш масіў выразаў цяпер аднамерны, наш isPalindrome па-ранейшаму з'яўляецца 2D-масівам.