पैलिंड्रोम विभाजन


कठिनाई स्तर मध्यम
में अक्सर पूछा वीरांगना Facebook गूगल माइक्रोसॉफ्ट
बैक ट्रैकिंग गहराई पहली खोज गतिशील प्रोग्रामिंग तार

समस्या का विवरण

एक स्ट्रिंग को देखते हुए, आवश्यक न्यूनतम संख्या में कटौती की आवश्यकता है जैसे कि विभाजन के सभी सब्सट्रेट पलिंड्रोम हैं। चूँकि हम अपने मूल स्ट्रिंग को अलग-अलग विभाजनों में काट रहे हैं, जैसे कि सभी सबस्ट्रिंग पलिंड्रोम्स हैं, इसलिए हम इस समस्या को पैलिंड्रोम विभाजन समस्या कहते हैं।

उदाहरण 

asaaaassss
2

स्पष्टीकरण: यहां, हम इनपुट स्ट्रिंग में कटौती कर सकते हैं आसा | आआ | ssss, इस प्रकार हमें दो कटौती की आवश्यकता है।

zxxzxxzyuy
1

स्पष्टीकरण: यहां, हम इनपुट स्ट्रिंग में कटौती कर सकते हैं zxxzxxz | युयो, इसलिए हमें एक ही कटौती की आवश्यकता है।

 

पॉलिंड्रोम विभाजन के लिए दृष्टिकोण

Naive दृष्टिकोण

पहली बात जो मन में आती है वह एक सरल पुनरावर्ती समाधान है। गौर कीजिए, हमारे पास लंबाई का एक स्ट्रिंग n है। अब, यदि स्ट्रिंग पैलिंड्रोम है, तो हम केवल उत्तर 0 को वापस कर सकते हैं, लेकिन यदि यह एक palindrome नहीं है। हम सभी संभावनाओं की कोशिश करते हैं, इसका मतलब है कि हम कोशिश कर रहे हैं कि हम 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 की एक स्ट्रिंग के साथ एक समस्या थी और फिर हमने अपनी समस्या को दो उप-प्रक्रमों में घटा दिया। यदि हम उपप्रकारों की संरचना देखते हैं तो वे निश्चित रूप से ओवरलैप भी होते हैं। तो, यह उपयोग करने का सुझाव देता है गतिशील प्रोग्रामिंग पहले के समाधान के घातीय समय जटिलता को कम करने के लिए ओ (एन ^ 3)। आंकड़ा लाल रंग में अतिव्यापी उपप्रभु दिखाता है। एक समान गतिशील प्रोग्रामिंग पैटर्न देखा जा सकता है मैट्रिक्स चेन गुणा समस्या, जहां हम पहले छोटे उपप्रकारों को हल करते हैं और फिर मूल समस्या को हल करने के लिए उनके परिणाम को जोड़ते हैं।

Palindrome विभाजन के लिए कोड

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

समय जटिलता: ओ (एन ^ 3)

पहला लूप 1 से n तक चलता है (len = 1 से len = n)

नेस्टेड लूप, सबप्रॉब्लम (i) के लिए स्टार्ट इंडेक्स को 0 से n-len तक चलाता है

सबसे आंतरिक लूप, जो k और k + 1 के बीच कटौती के सूचकांक को बताता है, वह भी i से j तक चलता है। 

इस प्रकार, सबसे खराब स्थिति में, समय की जटिलता को ओ (एन ^ 3) कहा जाता है।

अंतरिक्ष जटिलता: O (N ^ 2)

हमारे पास दो एरेप्लेन्ड्रोम और कट हैं जो 2 डी एरेज़ हैं और इस प्रकार हमारे पास ओ (एन ^ 2) स्पेस जटिलता है।

 

Palindrome विभाजन के लिए अनुकूलित समाधान

हम समय की जटिलता को और कम कर सकते हैं ओ (एन ^ 2), इलिपिंड्रोम मैट्रिक्स को प्री-कंप्यूटिंग करके। फिर i से j के स्थान पर कटौती के लिए भंडारण के बजाय (जहां मैं बाईं सीमा है और जम्मू किसी भी palindrome के विकल्प की सही सीमा है), हम कटिंग को एक एकल-आयामी सरणी के रूप में संग्रहीत करते हैं, जो प्रारंभ करने के लिए आवश्यक न्यूनतम संख्या में कटौती करता है। 0 से मैं। आंतरिक लूप j से 0 से i-1 पर चलता है, जहाँ हम जाँचते हैं कि क्या विकल्प [j, i] है? अगर सबस्ट्रिंग पैलिंड्रोम है, तो सबस्ट्रिंग [j, i] में [०, जे -१] [१] के विकल्प के समान ही कट्स हैं, इसलिए, हम सिर्फ जम्मू से j के लिए सभी विकल्पों में से न्यूनतम को संग्रहीत करके उत्तर को अपडेट करते हैं। 0 से आई -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);
    }
  }
}

समय जटिलता: ओ (एन ^ 2)

यदि हमने इंडेक्स से जम्मू तक का तालमेल किया है तो हमने स्टोर करने के लिए O (N ^ 2) लिया।

न्यूनतम कटौती के लिए O, (N ^ 2)। चूंकि बाहरी लूप स्ट्रिंग की पूरी लंबाई पर चलता है और आंतरिक लूप 0 से i-1 तक चलता है।

इस प्रकार, रनटाइम कुल ओ (एन ^ 2) बना रहा है।

अंतरिक्ष जटिलता: ओ (एन ^ 2)

भले ही हमारी कटौती सरणी अब एकल-आयामी है, फिर भी हमारा isPalindrome 2 डी सरणी है।