پالینډروم تقسیم


مشکل کچه منځني
په مکرر ډول دننه پوښتل کیږي ترلاسه کړئ Amazon فیسبوک د ګوګل د Microsoft
شاته تګ ژور لومړی لټون متحرک برنامې تار

ستونزه بیان

یو سلسله ورکړل شوی ، د اړینو قطعاتو لږترلږه شمیره ومومئ لکه د پارټیشنونو ټولې سبسټریګونه پالنډرومونه دي. له هغه ځایه چې موږ خپل اصلي تار په بیلابیلو پارټونو کې کاږو لکه دا چې ټولې سبسټرینګونه پالنډرومونه دي ، نو موږ دې ستونزې ته د پالینډروم ویش ستونزه وایو.

بېلګه 

asaaaassss
2

توضیحي: دلته ، موږ کولی شو د ننوتلو مزي لکه څنګه چې غوړ کړو آسا | aaa | ssss ، پدې توګه موږ دوه کټیو ته اړتیا لرو.

zxxzxxzyuy
1

توضیحي: دلته ، موږ کولی شو د ننوتلو مزي لکه څنګه چې غوړ کړو zxxzxxz | یو، نو موږ یو کټ ته اړتیا لرو.

 

د پالندوم پارټینګ کولو لپاره لاره

بې لارې چلند

لومړی شی چې ذهن ته راځي د ساده تکراري حل دی. په پام کې ونیسئ ، موږ د اوږدوالي تار لرو n. اوس ، که تار پالینډروم وي موږ کولی شو ځواب په ساده ډول 0 ته راستون کړو مګر که دا پالینډروم نه وي. موږ ټول امکانات هڅه کوو ، د دې معنا زما د دې معنی ده چې موږ د Kth شاخص کې په دوه برخو کې تار مټ کولو هڅه کوو او بیا د کی left برخې او ښیې برخې لپاره په جلا ډول حل کوو. دا حل بالکل درست دی مګر که څه هم اغیزناک ندي.

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

پالینډروم تقسیم

اغیزمنه کړنلاره

تر دې دمه ، موږ یو ساده حل پوهیږو چې کی the اړخ او د تار ښي برخه حل کوي پداسې حال کې چې د دوی ترمینځ کټ کیږدو. نو ، موږ کولی شو ووایو چې په پیل کې موږ د اندازې 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;
  }
}

جاوا کوډ

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 څخه تر ن (لین = 1 پورې لین = n) پورې تیریږي

د ځورونې لوپ د فرعي ستونزو لپاره د پیل شاخص په ګوته کوي (i) د 0 څخه تر نی پورې

ترټولو داخلي لوپ ، کوم چې د k او k + 1 تر مینځ د کټ شاخص ویل کیږي ، له i څخه تر j پورې هم تیریږي. 

پدې توګه ، په خورا بد حالت کې ، د وخت پیچلتیا O (N ^ 3) ته ویل کیږي.

د ځای پیچلتیا: O (N ^ 2)

موږ دوه اریزونه لرو پالینډروم او کټونه لرو چې د 2D ارې دي او پدې توګه موږ د O (N ^ 2) ځای پیچلتیا لرو.

 

د پالینډروم ویشلو لپاره غوره حل

موږ کولی شو د وخت پیچلتیا نوره هم کمه کړو O (N ^ 2)، دمخه کمپیوټر کولو لخوا isPalindrome میټریکس. بیا د I څخه j ته سبسټرینګ لپاره د کټونو ذخیره کولو پرځای (چیرته چې زه کی left اړخ ته حد او 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;
  }
}

جاوا کوډ

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 سرنی دی.