सी++ में पालिंड्रोम सबस्ट्रिंग क्वेरीज़

इस ट्यूटोरियल में, हमें दिए गए स्ट्रिंग के पैलिंड्रोम सबस्ट्रिंग प्रश्नों को हल करने की आवश्यकता है। सी ++ में नियमित प्रश्नों को हल करने की तुलना में पैलिंड्रोम सबस्ट्रिंग प्रश्नों को हल करना कहीं अधिक जटिल है। इसके लिए कहीं अधिक जटिल कोड और तर्क की आवश्यकता है।

इस ट्यूटोरियल में, हमें सबस्ट्रिंग [L...R] प्रश्नों की स्ट्रिंग str और Q संख्या प्रदान की जाती है, प्रत्येक में दो मान L और R होते हैं। हमारा लक्ष्य एक प्रोग्राम लिखना है जो यह निर्धारित करने के लिए प्रश्नों को हल करेगा कि सबस्ट्रिंग [L] है या नहीं। ..R] एक पालिंड्रोम है। हमें यह तय करना होगा कि एल से आर की सीमा के भीतर गठित सबस्ट्रिंग प्रत्येक प्रश्न को हल करने के लिए एक पैलिंड्रोम है या नहीं। उदाहरण के लिए -

Let's input "abbbabaaaba" as our input string.
The queries were [3, 13], [3, 11], [5, 8], [8, 12]
It is necessary to determine whether the substring is a plaindrome
A palindrome is "abaaabaaaba" (3, 13) .
It is not possible to write "baaa" as a palindrome [3, 11].
As in [5, 8]: "aaab" cannot be a palindrome.
There is a palindrome in "baaab" ([3, 12]).

समाधान खोजने के लिए दृष्टिकोण

बेवकूफ तरीका

यहां, हमें यह जांच कर एक पैलिंड्रोम खोजना होगा कि क्या सबस्ट्रिंग इंडेक्स रेंज एल से आर तक है। इसलिए, हमें सभी सबस्ट्रिंग प्रश्नों को एक-एक करके जांचना होगा और यह निर्धारित करना होगा कि वे पैलिंड्रोम हैं या नहीं। चूंकि Q प्रश्न हैं और प्रत्येक प्रश्न का उत्तर देने में 0(N) समय लगता है। सबसे खराब स्थिति में 0(Q.N) समय लगता है।

उदाहरण

#include <bits/stdc++.h>
using namespace std;
int isPallindrome(string str){
   int i, length;
   int flag = 0;
   length = str.length();
   for(i=0;i < length ;i++){
      if(str[i] != str[length-i-1]) {
         flag = 1; break;
      }
   }
   if (flag==1)
      return 1;
   return 0;
}
void solveAllQueries(string str, int Q, int query[][2]){
   for(int i = 0; i < Q; i++){
      isPallindrome(str.substr(query[i][0] - 1, query[i][1] - 1))?                  cout<<"Palindrome\n":cout<<"Not palindrome!\n";
   }
}
int main() {
   string str = "abccbeba"; int Q = 3;
   int query[Q][2] = {{3, 5}, {5, 7}, {2, 1}};
   solveAllQueries(str, Q, query);
   return 0;
}

आउटपुट

Palindrome
Palindrome
Not palindrome!

गतिशील प्रोग्रामिंग विधि

समस्या को हल करने के लिए एक गतिशील प्रोग्रामिंग दृष्टिकोण का उपयोग करना एक कुशल विकल्प है। हल करने के लिए, हमें एक DP सरणी बनाने की आवश्यकता होगी, जो एक द्वि-आयामी सरणी है जिसमें एक बूलियन मान होता है जो दर्शाता है कि क्या सबस्ट्रिंग[i...j] DP[i][j] के लिए एक पैलिंड्रोम है।

यह DP मैट्रिक्स बनाया जाएगा, और प्रत्येक क्वेरी के लिए सभी L-R मानों की जाँच की जाएगी।

उदाहरण

#include <bits/stdc++.h>
using namespace std;
void computeDP(int DP[][50], string str){
   int length = str.size();
   int i, j;
   for (i = 0; i < length; i++) {
      for (j = 0; j < length; j++)
         DP[i][j] = 0;
   }
   for (j = 1; j <= length; j++) {
      for (i = 0; i <= length - j; i++) {
         if (j <= 2) {
            if (str[i] == str[i + j - 1])
               DP[i][i + j - 1] = 1;
         }
         else if (str[i] == str[i + j - 1])
            DP[i][i + j - 1] = DP[i + 1][i + j - 2];
      }
   }
}
void solveAllQueries(string str, int Q, int query[][2]){
   int DP[50][50];
   computeDP(DP, str);
   for(int i = 0; i < Q; i++){
      DP[query[i][0] - 1][query[i][1] - 1]?cout
      <<"not palindrome!\n":cout<<"palindrome!\n";
   }
}
int main() {
   string str = "abccbeba"; int Q = 3;
   int query[Q][2] = {{3, 5}, {5, 7}, {2, 1}};
   solveAllQueries(str, Q, query);
   return 0;
}

आउटपुट

palindrome!
not palindrome!
palindrome!

निष्कर्ष

इस ट्यूटोरियल में, हमने सीखा कि c++ कोड के साथ पैलिंड्रोम सबस्ट्रिंग प्रश्नों को कैसे हल किया जाए। हम इस कोड को जावा, पायथन और अन्य भाषाओं में भी लिख सकते हैं। यह कोड सबसे जटिल और लंबे कोडों में से एक था। पैलिंड्रोम प्रश्न नियमित प्रतिस्थापन प्रश्नों की तुलना में कठिन होते हैं, और उन्हें बहुत सटीक तर्क की आवश्यकता होती है। हमें उम्मीद है कि आपको यह ट्यूटोरियल मददगार लगा होगा।