एक स्ट्रिंग के सभी Palindromic विभाजन मुद्रित करें  


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

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

"स्ट्रिंग के सभी पलिंड्रोमिक विभाजन मुद्रित करें" समस्या में हमने दिया है स्ट्रिंग "एस"। एस के सभी संभव पैलिंड्रोमिक विभाजन को मुद्रित करने के लिए एक कार्यक्रम लिखें। एक पैलेंड्रोम एक शब्द, संख्या, वाक्यांश, या वर्णों का एक और अनुक्रम है जो आगे की ओर उसी तरह पढ़ता है, जैसे कि मैडम या रेसकार।

इनपुट प्रारूप  

दी गई स्ट्रिंग "s" वाली पहली और एकमात्र एक लाइन है।

आउटपुट स्वरूप  

एन लाइनों को प्रिंट करें जहां स्ट्रिंग "एस" के विभाजन वाले प्रत्येक लाइन। यहाँ N, स्ट्रिंग "s" के विभिन्न विभाजनों की कुल संख्या है।

की कमी  

  • 1 <= | s | <= 16
  • s [i] एक कम अंग्रेजी अक्षर होना चाहिए

उदाहरण  

aab
a a b 
aa b

दृष्टिकोण  

विचार किसी दिए गए स्ट्रिंग के सभी संभावित सबस्ट्रिंग उत्पन्न करने और संभावित उम्मीदवार होने पर प्रत्येक संभावना का विस्तार करने का है। पहली बात जो हमारे दिमाग में आती है वह है गहराई पहली खोज। पहले गहराई में, हम निर्धारित लक्ष्य हासिल होने तक संभावित उम्मीदवारों का पुनरावर्ती विस्तार करते हैं। उसके बाद, हम अगले संभावित उम्मीदवार का पता लगाने के लिए पीछे हटते हैं।

बैक ट्रैकिंग वृद्धिशील रूप से हल के लिए उम्मीदवारों का निर्माण और उम्मीदवारों (पीछे) को छोड़ दें यदि यह शर्त को पूरा नहीं करता है। नीचे दिए गए एल्गोरिथ्म के कुछ चरण दिए गए हैं:

  • चुनें: संभावित उम्मीदवार चुनें। यहां, हमारे संभावित उम्मीदवार सभी सबस्ट्रिंग हैं जो दिए गए स्ट्रिंग से उत्पन्न हो सकते हैं।
  • बाधा: एक बाधा को परिभाषित करें जिसे चुने हुए उम्मीदवार द्वारा संतुष्ट होना चाहिए। इस मामले में, बाधा यह है कि स्ट्रिंग एक पैलिंड्रोम होना चाहिए।
  • लक्ष्य: हमें उस लक्ष्य को परिभाषित करना चाहिए जो निर्धारित करता है कि आवश्यक समाधान मिल गया है और हमें पीछे हटना चाहिए। यहां, हमारा लक्ष्य हासिल किया जाता है अगर हम स्ट्रिंग के अंत तक पहुंच गए हैं।
यह भी देखें
स्टॉक स्पैन समस्या

स्ट्रिंग के सभी Palindromic विभाजन प्रिंट के लिए एल्गोरिदम  

यहां, हम गहराई से खोज फैशन में स्ट्रिंग पर पुनरावृत्ति करते हैं। प्रत्येक पुनरावर्ती कॉल के लिए, स्ट्रिंग के शुरुआती सूचकांक को शुरुआत के रूप में दिया गया है।

  1. Iteratively सभी संभावित सबस्ट्रिंग की शुरुआत करते हैं सूचकांक।   सूचकांक वृद्धि  स्ट्रिंग के अंत तक।
  2. उत्पन्न किए गए प्रत्येक विकल्प के लिए, जांचें कि क्या यह एक तालमेल है।
  3. यदि सबस्ट्रिंग एक palindrome है, तो विकल्प एक संभावित उम्मीदवार है। के विकल्प में जोड़ें और शेष सबरिंग पर गहराई से पहली खोज करें। यदि वर्तमान सबस्ट्रिंग इंडेक्स पर समाप्त होता है , अंत + १ बन जाता है  अगले पुनरावर्ती कॉल के लिए सूचकांक।
  4. यदि अनुक्रमणिका स्ट्रिंग की लंबाई से अधिक या उसके बराबर है और पीछे जोड़ देता है  परिणाम के लिए।

कार्यान्वयन  

स्ट्रिंग के सभी पलिंड्रोमिक विभाजन प्रिंट के लिए C ++ प्रोग्राम

#include <bits/stdc++.h>

using namespace std;

bool check(string &s, int l, int r) 
{
    while (l < r) 
    {
        if (s[l++] != s[r--]) return false;
    }
    return true;
}
    
void dfs(vector<vector<string>> &r, string &s, int start, vector<string> &c) 
{
    if(start >= s.length())
    {
        r.push_back(c);
    }
    for(int i = start;i < s.length(); i++) 
    {
        if(check(s, start, i)) 
        {
            c.push_back(s.substr(start, i - start + 1));
            dfs(r, s, i + 1, c);
            c.pop_back();
        }
    }
}

int main()
{
   string s;
   cin>>s;
   vector<vector<string>> result;
   vector<string> current;
   dfs(result, s, 0, current);
   for(int i=0;i<result.size();i++)
   {
       for(int j=0;j<result[i].size();j++)
       {
           cout<<result[i][j]<<" ";
       }
       cout<<endl;
   }
   return 0;
}

स्ट्रिंग के सभी पलिंडोमिक विभाजन प्रिंट के लिए जावा कार्यक्रम

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

class sum
{ 
        static boolean isPalindrome(String s, int low, int high) 
        {
            while (low < high) {
                if (s.charAt(low++) != s.charAt(high--)) return false;
            }
            return true;
        }
        static void dfs(int start, List<List<String>> r, List<String> c, String s) 
        {
            if (start >= s.length()) 
            {
                r.add(new ArrayList<String>(c));
            }
            for (int end = start; end < s.length(); end++) {
                if(isPalindrome(s, start, end)) 
                {
                    c.add(s.substring(start, end + 1));
                    dfs(end + 1, r, c, s);
                    c.remove(c.size() - 1);
                }
            }
        }
        
  public static void main(String[] args) 
  { 
    Scanner sr = new Scanner(System.in); 
                String s = sr.next();
                List<List<String>> r = new ArrayList<List<String>>();
                List<String> c = new ArrayList<String>();
                dfs(0, r, c, s);
                for(int i=0;i<r.size();i++)
                {
                    for(int j=0;j<r.get(i).size();j++)
                    {
                        System.out.print(r.get(i).get(j).toString());
                        System.out.print(" ");
                    }
                    System.out.println();
                }
  } 
} 
racecar
r a c e c a r 
r a cec a r 
r aceca r 
racecar

एक स्ट्रिंग के सभी Palindromic विभाजन प्रिंट के लिए जटिलता विश्लेषण  

समय जटिलता

O (N ^ (2 * N)) जहां N स्ट्रिंग की लंबाई "s" है। यह सबसे खराब स्थिति वाला समय जटिलता है जब सभी संभावित सब्सट्रेट पलिंड्रोम हैं।

यह भी देखें
हाथापाई स्ट्रिंग

अंतरिक्ष जटिलता

पर) जहां N स्ट्रिंग की लंबाई "s" है। S = aaa के लिए, पुनरावर्ती कॉल स्टैक की अधिकतम गहराई 3 है जो एन के बराबर है।