समस्या विवरण
इस समस्या में, हमें एक स्ट्रिंग str, Q क्वेरीज दी गई हैं जिनमें प्रत्येक में सबस्ट्रिंग [L...R] के लिए दो मान L और R होते हैं। हमारा कार्य सबस्ट्रिंग [L...R] के पालिंड्रोम होने या न होने की जांच के लिए क्वेरीज को हल करने का प्रोग्राम बनाना है।
समस्या विवरण - प्रत्येक क्वेरी को हल करने के लिए, हमें इंडेक्स रेंज L से R से बने सबस्ट्रिंग को ढूंढना होगा। और जांचना होगा कि सबस्ट्रिंग पालिंड्रोम है या नहीं।
उदाहरण
str = "abccbeba", Q = 3
Query[][] = {{1, 4}, {0, 6}, {4, 6}}
आउटपुट
Palindrome Not Palindrome Palindrome
व्याख्या
दिए गए सबस्ट्रिंग्स के लिए सभी सबस्ट्रिंग बनाना: Substring[1...4] = "bccb", यह एक पालिंड्रोम है Substring[0...6] = "abccbeb", यह एक पालिंड्रोम नहीं है Substring[4...6] = "beb", यह एक पालिंड्रोम है
हल करने का दृष्टिकोण
समस्या का एक सरल हल प्रत्येक क्वेरी को हल करना है। इसे हल करने के लिए, हमें इंडेक्स रेंज L से R से सबस्ट्रिंग ढूंढनी होगी। और जांचना होगा कि सबस्ट्रिंग पालिंड्रोम है या नहीं।
उदाहरण 1: नैव दृष्टिकोण
#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] - query[i][0] + 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: डायनामिक प्रोग्रामिंग दृष्टिकोण (कुशल)
समस्या का एक कुशल हल डायनामिक प्रोग्रामिंग दृष्टिकोण का उपयोग करना है। हल करने के लिए, हमें एक DP ऐरे बनाना होगा, एक 2-D ऐरे जो एक बूलियन मान संग्रहीत करता है जो दर्शाता है कि सबस्ट्रिंग [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 << "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!