सी++ में न्यूनतम शब्द विराम समस्या

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

आइए इसके लिए विभिन्न इनपुट आउटपुट परिदृश्य देखें -

में - स्ट्रिंग शब्द [] ={"हैलो", "नर्क", "बताना", "वेल", "बेल", "बॉल", "ऑल"}

बाहर -न्यूनतम शब्द विराम है:1

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

में - स्ट्रिंग शब्द [] ={"हैलो", "नर्क", "बताना", "वेल", "बेल", "बॉल", "ऑल"}

बाहर -न्यूनतम शब्द विराम है:1

स्पष्टीकरण - हमें कई शब्दों के साथ दिया गया है। अब हम दो स्ट्रिंग्स यानी नर्क और कुएं के संयोजन को पास करेंगे और जुड़े हुए शब्द को तोड़ेंगे। तो, हेलवेल को "हेल वेल" के रूप में विभाजित किया जा सकता है जो कि पहला ब्रेक है और दोनों शब्द मान्य हैं। अब, हम इसे और आगे तोड़ेंगे यानी "वह ठीक हो जाएगा" जो कोई वैध स्ट्रिंग नहीं बना रहा है। तो आउटपुट 1 है।

नीचे दिए गए प्रोग्राम में इस्तेमाल किया गया तरीका इस प्रकार है

• शब्दों की स्ट्रिंग सरणी इनपुट करें और आकार () फ़ंक्शन का उपयोग करके आकार की गणना करें।

• एक चर को min_val के रूप में घोषित करें और इसे अधिकतम संभव मान के रूप में INT_MAX पर सेट करें।

• रूट के रूप में टाइप स्ट्रक्चर का ऑब्जेक्ट बनाएं और इसे कॉल पर फंक्शन रिटर्न_नोड ()

  पर सेट करें

• एक सरणी के आकार तक i से 0 तक के लिए लूप प्रारंभ करें। लूप के अंदर, एक पेड़ में नोड डालने के लिए फ़ंक्शन Insert_Node() को कॉल करें।

• न्यूनतम शब्द विराम की गणना के लिए न्यूनतम_ब्रेक () को कॉल करें और अंतिम परिणाम प्रिंट करें।

• डेटा के रूप में शब्दों के साथ नोड्स के पेड़ के निर्माण के लिए एक संरचना घोषित करें।

  • ptr[total_Alpha] के रूप में पॉइंटर्स की एक सरणी और चेक के रूप में एक बूलियन वैरिएबल बनाएं।

• रिटर्न_नोड के अंदर (शून्य)

  • Ptr_1 के रूप में टाइप स्ट्रक्चर का पॉइंटर बनाएं। सेट करें ptr_1->झूठे के रूप में जांचें

  • लूप फॉर को i से 0 तक प्रारंभ करें जब तक कि मैं Total_Alpha से कम नहीं हो जाता। लूप के अंदर, ptr_1->ptr[i] को NULL

    . पर सेट करें

  • वापसी ptr_1

• समारोह के अंदर Insert_Node(struct node* root, string val)

  • ptr_1 के रूप में एक पॉइंटर बनाएं और इसे रूट पर सेट करें।

  • लूप फॉर i से 0 तक val.length() तक प्रारंभ करें। लूप के अंदर, कुंजी को val[i] - 'a' के रूप में सेट करें और जांचें कि IF ptr_1->ptr[key] NULL है, फिर ptr_1->ptr[key] को फंक्शन रिटर्न_नोड () के कॉल पर सेट करें।

  • ptr_1 को ptr_1->ptr[key] पर सेट करें और ptr_1->सही पर जांचें

• फंक्शन के अंदर मिनिमम_ब्रेक (स्ट्रक्चर नोड* रूट, स्ट्रिंग वैल, इंट फर्स्ट, इंट* टेम्प, इंट ए =0)

  • ptr_1 के रूप में एक पॉइंटर बनाएं और इसे रूट पर सेट करें।

  • पहले IF =val.length() चेक करें, फिर *temp को C++ के इनबिल्ट फंक्शन पर कॉल करने के लिए सेट करें जो कि min(*temp, a-1) है और रिटर्न करें।

  • एक वैल की लंबाई से कम तक i से पहले तक के लिए लूप प्रारंभ करें। लूप के अंदर, पता को वैल [i] - 'ए' के ​​रूप में सेट करें और जांचें कि क्या ptr_1->ptr [पता] शून्य है, फिर वापस आएं।

  • जाँच करें IF ptr_1->ptr[address]->चेक सत्य है तो न्यूनतम_ब्रेक पर कॉल करें (रूट, वैल, i + 1, अस्थायी, a + 1)

  • ptr_1 को ptr_1->ptr[पता] पर सेट करें।

उदाहरण

#include <bits/stdc++.h>
using namespace std;
#define total_Alpha 26
//create a tree of nodes of words
struct node{
   struct node* ptr[total_Alpha];
   bool check;
};
//Return tree with all nodes
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;
}
//insert values to the nodes in a tree
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;
}
//calculate the minimum word break
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