C++ में न्यूनतम वर्ड ब्रेक समस्या

हमें किसी भी दिए गए आकार के शब्दों की एक सरणी स्ट्रिंग दी गई है और कार्य शब्दों को सभी संभावित तरीकों से तोड़ना है ताकि ब्रेक के बाद बनी स्ट्रिंग एक वैध स्ट्रिंग हो और हमें समस्या के अनुसार ऐसे सभी न्यूनतम वर्ड ब्रेक की गणना करनी है।

विभिन्न इनपुट-आउटपुट परिदृश्य देखते हैं:

इनपुट: string word[] = {"Hello", "Hell", "tell", "well", "bell", "ball", "all"}

आउटपुट: न्यूनतम वर्ड ब्रेक है: 1

व्याख्या: हमें कई शब्द दिए गए हैं। अब हम दो स्ट्रिंग्स Hell और all के संयोजन को पास करेंगे और संयुक्त शब्द को तोड़ेंगे। तो, Hellall को "Hell all" के रूप में विभाजित किया जा सकता है जो पहला ब्रेक है और दोनों शब्द वैध हैं। अब, हम इसे आगे तोड़ेंगे यानी "He ll aa" जो कोई वैध स्ट्रिंग नहीं बनाता। इसलिए आउटपुट 1 है।

इनपुट: string word[] = {"Hello", "Hell", "tell", "well", "bell", "ball", "all"}

आउटपुट: न्यूनतम वर्ड ब्रेक है: 1

व्याख्या: हमें कई शब्द दिए गए हैं। अब हम दो स्ट्रिंग्स Hell और well के संयोजन को पास करेंगे और संयुक्त शब्द को तोड़ेंगे। तो, Hellwell को "Hell well" के रूप में विभाजित किया जा सकता है जो पहला ब्रेक है और दोनों शब्द वैध हैं। अब, हम इसे आगे तोड़ेंगे यानी "He ll well" जो कोई वैध स्ट्रिंग नहीं बनाता। इसलिए आउटपुट 1 है।

नीचे दिए गए प्रोग्राम में उपयोग किया गया दृष्टिकोण:

• शब्दों की स्ट्रिंग सरणी इनपुट करें और size() फंक्शन का उपयोग करके आकार गणना करें।
• min_val नामक एक वेरिएबल घोषित करें और इसे INT_MAX पर सेट करें जो अधिकतम संभव मान है।
• root नामक स्ट्रक्चर प्रकार का एक ऑब्जेक्ट बनाएं और इसे Return_Node() फंक्शन कॉल पर सेट करें।
• i को 0 से सरणी के आकार तक लूप चलाएं। अंदर, नोड को ट्री में डालने के लिए Insert_Node() फंक्शन कॉल करें।
• न्यूनतम वर्ड ब्रेक की गणना करने और अंतिम परिणाम प्रिंट करने के लिए Minimum_Break() कॉल करें।
• शब्दों को डेटा के रूप में नोड्स का ट्री बनाने के लिए एक स्ट्रक्चर घोषित करें।
  • ptr[total_Alpha] के रूप में पॉइंटर्स की एक सरणी और check के रूप में एक बूलियन वेरिएबल बनाएं।
• फंक्शन Return_Node(void) के अंदर:
  • ptr_1 नामक स्ट्रक्चर प्रकार का एक पॉइंटर बनाएं। ptr_1->check को false पर सेट करें।
  • i को 0 से total_Alpha से कम तक लूप चलाएं। अंदर, ptr_1->ptr[i] को NULL पर सेट करें।
  • ptr_1 लौटाएं।
• फंक्शन Insert_Node(struct node* root, string val) के अंदर:
  • ptr_1 नामक एक पॉइंटर बनाएं और इसे root पर सेट करें।
  • i को 0 से val.length() से कम तक लूप चलाएं। अंदर, key को val[i] - 'a' पर सेट करें और जांचें यदि ptr_1->ptr[key] NULL है तो ptr_1->ptr[key] को Return_Node() फंक्शन कॉल पर सेट करें।
  • ptr_1 को ptr_1->ptr[key] पर सेट करें और ptr_1->check को true पर सेट करें।
• फंक्शन Minimum_Break(struct node* root, string val, int first, int* temp, int a = 0) के अंदर:
  • ptr_1 नामक एक पॉइंटर बनाएं और इसे root पर सेट करें।
  • जांचें यदि first = val.length() तो *temp को C++ के इनबिल्ट फंक्शन min(*temp, a - 1) कॉल पर सेट करें और लौटाएं।
  • i को first से val.length() से कम तक लूप चलाएं। अंदर, address को val[i] - 'a' पर सेट करें और जांचें यदि ptr_1->ptr[address] null है तो लौटाएं।
  • जांचें यदि ptr_1->ptr[address]->check true है तो Minimum_Break(root, val, i + 1, temp, a + 1) कॉल करें।
  • ptr_1 को ptr_1->ptr[address] पर सेट करें।

उदाहरण

#include <bits/stdc++.h>
using namespace std;

#define total_Alpha 26

// शब्दों के नोड्स का ट्री बनाएं
struct node {
    struct node* ptr[total_Alpha];
    bool check;
};

// सभी नोड्स के साथ ट्री लौटाएं
struct node* Return_Node(void) {
    struct node* ptr_1 = new node;
    ptr_1->check = false;
    for (int i = 0; i < total_Alpha; i++) {
        ptr_1->ptr[i] = NULL;
    }
    return ptr_1;
}

// ट्री में नोड्स में मान डालें
void Insert_Node(struct node* root, string val) {
    struct node* ptr_1 = root;
    for(int i = 0; i < val.length(); i++) {
        int key = val[i] - 'a';
        if(!ptr_1->ptr[key]) {
            ptr_1->ptr[key] = Return_Node();
        }
        ptr_1 = ptr_1->ptr[key];
    }
    ptr_1->check = true;
}

// न्यूनतम वर्ड ब्रेक की गणना करें
void Minimum_Break(struct node* root, string val, int first, int* temp, int a = 0) {
    struct node* ptr_1 = root;
    if(first == val.length()) {
        *temp = min(*temp, a - 1);
        return;
    }
    for(int i = first; i < val.length(); i++) {
        int address = val[i] - 'a';
        if(!ptr_1->ptr[address]) {
            return;
        }
        if(ptr_1->ptr[address]->check) {
            Minimum_Break(root, val, i + 1, temp, a + 1);
        }
        ptr_1 = ptr_1->ptr[address];
    }
}

int main() {
    string word[] = {"Hello", "Hell", "tell", "well", "bell", "ball", "all"};
    int size = sizeof(word) / sizeof(word[0]);
    int min_val = INT_MAX;
    struct node* root = Return_Node();
    for (int i = 0; i < size; i++) {
        Insert_Node(root, word[i]);
    }
    Minimum_Break(root, "Hellall", 0, &min_val, 0);
    cout << "Minimum Word Break is: " << min_val;
    return 0;
}

आउटपुट

यदि हम उपरोक्त कोड चलाते हैं तो यह निम्नलिखित आउटपुट उत्पन्न करेगा:

Minimum Word Break is: 1