پلنڊروم ورها Partي


تڪليف جي سطح وچولو
بار بار پڇڻ ۾ Amazon ڪريو گوگل Microsoft جي
واپسي گہرائي پهرين ڳولا متحرڪ پروگرامنگ اسٽرنگ

مسئلي جو بيان

هڪ جملو ڏنو ، گهٽ ۾ گهٽ ڪٽ جي گهرج گهربل آهي ته جيئن سڀني حصن جا حصا پيلنڊروم آهن. جئين اسان پنهنجي اصلي اسٽرنگ کي مختلف ڊويزنن ۾ کٽيندا آهيون ، جيئن ته سڀ ذريعا هوندا آهن.

مثال 

asaaaassss
2

وضاحت: هتي ، اسان انٽ سٽرنگ ڪٽ ڪري سگهو ٿا آسا | اا | ايس ايس ايس ، تنهنڪري اسان کي ٻه ڪٽ جي ضرورت آهي.

zxxzxxzyuy
1

وضاحت: هتي ، اسان انٽ سٽرنگ ڪٽ ڪري سگهو ٿا ايڪسڪسيمڪسز | يارتنهنڪري اسان کي هڪ ڪٽڻ جي ضرورت آهي.

 

پالينڊروم ورشن لاءِ روش

نائي اچڻ وارو

پهرين شيء جيڪا ذهن تي اچي ٿي ، هڪ سادي بار بار حل آهي. غور ڪريو ، اسان کي ڊيگهه جو هڪ جملو آهي ن. هاڻي ، جيڪڏهن اهو تار palindrome آهي اسان صرف جواب 0 واپس ڪري سگهو ٿا پر جيڪڏهن اهو هڪ palindrome نه آهي اسان سڀني امکانات جي ڪوشش ڪريون ٿا ، انهي جو مطلب ته آئون ڪيٿ انڊيڪس ۾ ٻن حصن ۾ تار کي ڪٽائڻ جي ڪوشش ڪريون ٿا ۽ پوءِ الڳ ۽ کاٻي حصي کي الڳ طور تي ٻيهر حل سان حل ڪريو. اهو حل بلڪل صحيح آهي پر ڪارآمد ناهي.

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

پلنڊروم ورها Partي

ايڏي موثر رستو

هينئر تائين ، اسان هڪ سادو حل knowاڻون ٿا جيڪو تار جي کاٻي حصي ۽ سا partي حصي کي حل ڪري ٿو جڏهن انهن جي وچ ۾ ڪاٽ رکي. تنهن ڪري ، اسان اهو چئي سگهون ٿا ته شروعات ۾ اسان کي سائز اين جي اسٽرنگ سان مسئلو هو ۽ پوء اسان پنهنجو مسئلو گهٽ ڪري ڇڏيو ٻن ذيلي مسئلن ڏانهن. جيڪڏهن اسان ضمني نظام جي جوڙجڪ کي ڏسون ٿا ته اهي به ضرور مٿان چڙهندا آهن. تنهن ڪري ، انهي جي استعمال جو مشورو ڏئي ٿو متحرڪ پروگرامنگ اڳئين حل جي عارضي وقت جي پيچيدگي کي گھٽائڻ لاءِ اي (اين ^ 3). اھو شڪل ڏيکاري ٿو سرخ رنگ جي وڌيڪ ذيلي عنصر. هڪ جهڙو متحرڪ پروگرامنگ اندر ڏسي سگهجي ٿو ميٽرڪس چين جي ضرب جو مسئلو، جتي اسان پهريان نن smallerا ذيلي مسئلا حل ڪندا آهيون ۽ پوءِ انهن جي نتيجي کي گڏ ڪري اصل مسئلو حل ڪرڻ لاءِ.

پلنڌروم ورهاitionي لاءِ ڪوڊ

سي ++ ڪوڊ

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

وقت جي پيچيدگي: اي (اين ^ 3)

پهرين لوپ 1 کان ن تائين هلندو آهي (لين = 1 کان لين = اين)

ذيلي تقاضا (i) 0 کان n-len کان شروع ٿي انڊين پڌرو ڪري ٿو

گھڻي اندران وارو لوپ ، جيڪو ڪ ۽ k + 1 جي وچ ۾ کٽ جا انڊيڪس ٻڌائي ٿو ، I کان j تائين پڻ هلندو آهي. 

اھڙي طرح ، بدترين صورت ۾ ، وقت جي پيچيدگي چيو وڃي ٿي O (N ^ 3).

خلائي پيچيدگي: اي (اين ^ 2)

اسان وٽ ٻه ارٽون آهن پولينڊروم ۽ ڪٽيون جيڪا 2 ڊي ارٽريز آهن ۽ ان ڪري اسان وٽ اي (اين ^ 2) خلائي پيچيدگي آهي.

 

پلندروم ورهاromeي لاءِ بهتر حل

اسان وقت جي پيچيدگي کي گهٽ ڪري سگھون ٿا اي (اين ^ 2)، اڳين ڪمپيوٽنگ کان وٺي آئي پاليندروم ميٽرڪس. پوءِ I کان j کي سبٽرنگ لاءِ ڪٽ اسٽور ڪرڻ جي بدران (جتي مان کاٻي پاسي واري حد آهي ۽ j ڪنهن palindrome سبسٽنگ جي صحيح حد آهي) ، اسين ڪٽ کي هڪڙي محوري ڪناري جي طور تي محفوظ ڪريون ٿا سبٽرنگ جي شروعات لاءِ گهربل گهٽ ۾ گهٽ ڪٽ کي محفوظ ڪرڻ 0 کان آئون. اندروني لوپ 0 کان I-1 تائين هلندو آهي ، جتان اسان چڪاس ڪريون ٿا ته ڇا اهو سبسٽنگ [j ، i] پيلنڊروم آهي؟ جيڪڏهن سبسٽنگ پيلنڊروم آهي ته سبسٽنگ [j ، i] وٽ جيترو ڪٽ آهي جيترو سبسٽنگ [0 ، j-1] + 1. تنهن ڪري ، اسان ج کان جتن بابت گهٽ ۾ گهٽ آپشن کي محفوظ ڪندي جواب کي اپڊيٽ ڪيو ٿا. 0 کان -1. هن طريقي سان ، آخرڪار اسان وٽ گھٽ ۾ گهٽ ڪٽ جي ضرورت آهي اهڙي طرح سڀ ڀا palا پيلنڊرومس آهن.

سي ++ ڪوڊ

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

وقت جي پيچيدگي: اي (اين ^ 2)

اسان محفوظ ڪرڻ لاءِ O (N ^ 2) ورتو ، جيڪڏهن انڊيڪس کان ج تائين سبسٽسٽرونڊ آهي.

ڪ ، گهٽ ۾ گهٽ تعداد ڳولڻ لاءِ اي ، (اين ^ 2). جئين اسٽرنگ جي مڪمل ڊيگهه کان ٻاهرين لوپ هلندو آهي ۽ اندروني لوپ 0 کان آءِ 1 تائين هلندو آهي.

ان ڪري ، رينڊ ٽائيم کي ڪل او (N ^ 2) ٺاهڻ.

خلائي پيچيدگي: اي (اين ^ 2)

جيتوڻيڪ اسان جو کٽ جوڙ هاڻي واحد رخا آهي ، اسان جو پائيلنڊ اڃا تائين هڪ 2D صف آهي.