Computer >> कंप्यूटर ट्यूटोरियल >  >> प्रोग्रामिंग >> C++

C++ प्रोग्राम में सबस्ट्रिंग [L...R] के पालिंड्रोम होने की जांच के लिए क्वेरीज

समस्या विवरण

इस समस्या में, हमें एक स्ट्रिंग 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!
  1. C प्रोग्राम: जांचें कि सरणी पैलिंड्रोम है या नहीं (पुनरावृत्तीय) C प्रोग्राम: जांचें कि सरणी पैलिंड्रोम है या नहीं (पुनरावृत्तीय)

    पैलिंड्रोम सरणी एक सरणी पैलिंड्रोम है यदि यह आगे और पीछे से समान पढ़ी जाती है। उदाहरण सरणीपैलिंड्रोम? {1, 0, 0, 1}हाँ {1, 2, 3, 4, 5}नहीं {7}हाँ (एकल तत्व) {}हाँ (खाली) {1, 2, 2, 1}हाँ {1, 2, 3, 2, 1}हाँ पुनरावृत्तीय एल्गोरिदम दो पॉइंटर्स: start = 0, end = n-1 जब तक start < end: यदि ar

  1. C++ में जांचें कि बाइनरी ट्री ऊंचाई-संतुलित है या नहीं C++ में जांचें कि बाइनरी ट्री ऊंचाई-संतुलित है या नहीं

    एक बाइनरी ट्री ऊंचाई-संतुलित (height-balanced) होता है यदि प्रत्येक नोड के लिए उसके बाएं और दाएं सबट्री की ऊंचाई का निरपेक्ष अंतर 0 या 1 हो। दिए गए ट्री के लिए आउटपुट true (1) है। समाधान दृष्टिकोण (पोस्ट-ऑर्डर DFS) एक ग्लोबल फ्लैग ret = true रखें। dfs(node) फंक्शन नोड की ऊंचाई वापस करता है: यदि न

  1. C++ में STL का उपयोग करके जांचें कि क्या सरणी पैलिंड्रोम है या नहीं C++ में STL का उपयोग करके जांचें कि क्या सरणी पैलिंड्रोम है या नहीं

    n पूर्णांकों की एक सरणी arr[n] दी गई है, कार्य यह जांचना है कि क्या सरणी एक पैलिंड्रोम है या नहीं। हमें C++ में STL (स्टैंडर्ड टेम्पलेट लाइब्रेरी) का उपयोग करके यह कार्य करना है। C++ में STL (Standard Template Library) की एक विशेषता है, यह C++ टेम्पलेट कक्षाओं का एक समूह है जिसका उपयोग डेटा संरचना