इस समस्या में, हमें स्ट्रिंग str, Q प्रश्नों की संख्या दी गई है, जिनमें से प्रत्येक में दो मान L और R हैं, सबस्ट्रिंग [L...R] के लिए। हमारा काम यह जांचने के लिए क्वेरीज़ को हल करने के लिए एक प्रोग्राम बनाना है कि सबस्ट्रिंग [L…R] पैलिंड्रोम है या नहीं।
समस्या का विवरण - प्रत्येक प्रश्न को हल करने के लिए, हमें यह जांचना होगा कि एल से आर की सीमा के भीतर बनाया गया सबस्ट्रिंग एक पैलिंड्रोम है या नहीं।
समस्या को समझने के लिए एक उदाहरण लेते हैं,
इनपुट
str = “abccbeba” , Q = 3
Query[][] = {{1, 4}, {0, 6}, {4, 6}} आउटपुट
Palindrome Not Palindrome Palindrome
स्पष्टीकरण
Creating all substring for the given substrings : Substring[1...4] = “bccb”, it is a palindrome Substring[0...6] = “abccbeb”, it is a not palindrome Substring[4...6] = “beb”, it is a palindrome
समाधान दृष्टिकोण
समस्या का एक सरल समाधान प्रत्येक प्रश्न को हल करना है। इसे हल करने के लिए, हमें इंडेक्स रेंज एल से आर तक सबस्ट्रिंग खोजने की जरूरत है। और जांचें कि सबस्ट्रिंग एक पैलिंड्रोम है या नहीं।
हमारे समाधान की कार्यप्रणाली को दर्शाने वाला कार्यक्रम,
उदाहरण
#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] = {{1, 3}, {2, 5}, {4, 5}};
solveAllQueries(str, Q, query);
return 0;
} आउटपुट
Palindrome Not palindrome! Palindrome
यह एक भोला तरीका है लेकिन कारगर नहीं है।
समस्या का एक कुशल समाधान गतिशील प्रोग्रामिंग दृष्टिकोण का उपयोग कर रहा है। हल करने के लिए, हमें एक डीपी सरणी बनाने की आवश्यकता है जो एक 2-डी सरणी है जो एक बूलियन मान संग्रहीत करता है जो दर्शाता है कि क्या सबस्ट्रिंग [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] = {{1, 3}, {2, 5}, {4, 5}};
solveAllQueries(str, Q, query);
return 0;
} आउटपुट
palindrome! not palindrome! palindrome!