इस ट्यूटोरियल में, हमें दी गई स्ट्रिंग के पैलिंड्रोम सबस्ट्रिंग क्वेरीज़ को हल करने की आवश्यकता है। C++ में नियमित क्वेरीज़ को हल करने की तुलना में पैलिंड्रोम सबस्ट्रिंग क्वेरीज़ को हल करना कहीं अधिक जटिल है। इसके लिए कहीं अधिक जटिल कोड और तर्क की आवश्यकता होती है।
इस ट्यूटोरियल में, हमें स्ट्रिंग str और Q संख्या में सबस्ट्रिंग[L...R] क्वेरीज़ प्रदान की जाती हैं, प्रत्येक में दो मान L और R होते हैं। हमारा लक्ष्य एक प्रोग्राम लिखना है जो यह निर्धारित करने के लिए क्वेरीज़ को हल करेगा कि सबस्ट्रिंग[L...R] पैलिंड्रोम है या नहीं। हमें प्रत्येक क्वेरी को हल करने के लिए यह तय करना होगा कि रेंज L से R के भीतर बना सबस्ट्रिंग पैलिंड्रोम है या नहीं। उदाहरण के लिए -
आइए इनपुट स्ट्रिंग "abbbabaaaba" लें। क्वेरीज़ थीं [3, 13], [3, 11], [5, 8], [8, 12] यह निर्धारित करना आवश्यक है कि सबस्ट्रिंग पैलिंड्रोम है या नहीं "abaaabaaaba" (3, 13) एक पैलिंड्रोम है। "baaa" को पैलिंड्रोम [3, 11] के रूप में लिखना संभव नहीं है। [5, 8] में: "aaab" पैलिंड्रोम नहीं हो सकता। "baaab" ([3, 12]) में एक पैलिंड्रोम है।
समाधान खोजने का दृष्टिकोण
नाइव विधि
यहां, हमें यह जांचकर पैलिंड्रोम ढूंढना होगा कि क्या सबस्ट्रिंग इंडेक्स रेंज L से R से है। इसलिए, हमें सभी सबस्ट्रिंग क्वेरीज़ को एक-एक करके जांचना होगा और यह निर्धारित करना होगा कि वे पैलिंड्रोम हैं या नहीं। चूंकि Q क्वेरीज़ हैं और प्रत्येक क्वेरी का उत्तर देने में O(N) समय लगता है। सबसे खराब स्थिति में यह O(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++ कोड के साथ पैलिंड्रोम सबस्ट्रिंग क्वेरीज़ को हल करना सीखा। हम इस कोड को जावा, पायथन और अन्य भाषाओं में भी लिख सकते हैं। यह कोड सबसे जटिल और लंबे कोड में से एक था। पैलिंड्रोम क्वेरीज़ नियमित सबस्ट्रिंग क्वेरीज़ से कठिन होती हैं, और उन्हें बहुत सटीक तर्क की आवश्यकता होती है। हमें उम्मीद है कि आपको यह ट्यूटोरियल उपयोगी लगा।
