ปัญหาการแบ่งคำขั้นต่ำใน C ++

เราได้รับสตริงอาร์เรย์ของคำในขนาดที่กำหนด และภารกิจคือการแบ่งคำด้วยวิธีที่เป็นไปได้ทั้งหมด ซึ่งหลังจากการแบ่งสตริงที่ก่อตัวขึ้นควรเป็นสตริงที่ถูกต้อง และเราต้องคำนวณตัวแบ่งคำขั้นต่ำทั้งหมดตาม ปัญหา

ให้เราดูสถานการณ์อินพุตเอาต์พุตต่างๆ สำหรับสิ่งนี้ -

ใน − string word[] ={"Hello", "Hell", "tell", "well", "bell", "ball", "all" }

ออก − ตัวแบ่งคำขั้นต่ำคือ:1

คำอธิบาย − เราได้รับหลายคำ ตอนนี้เราจะผ่านการต่อกันของสองสตริงนั่นคือ นรกและทั้งหมด และจะทำลายคำที่ต่อกัน ดังนั้น Hellall สามารถแบ่งออกเป็น "Hellall" ซึ่งเป็นช่วงแรกและทั้งสองคำถูกต้อง ตอนนี้เราจะทำลายมันต่อไปเช่น "He ll aa" ซึ่งไม่ได้สร้างสตริงที่ถูกต้อง ผลลัพธ์ที่ได้คือ 1

ใน − string word[] ={"Hello", "Hell", "tell", "well", "bell", "ball", "all" }

ออก − ตัวแบ่งคำขั้นต่ำคือ:1

คำอธิบาย − เราได้รับหลายคำ ตอนนี้เราจะผ่านการต่อกันของสองสตริงนั่นคือ นรกและดี และจะทำลายคำที่ต่อกัน ดังนั้น Hellwell จึงสามารถแบ่งได้เป็น "Hell well" ซึ่งเป็นช่วงแรกและทั้งสองคำถูกต้อง ตอนนี้เราจะทำลายมันต่อไปเช่น "เขาสบายดี" ซึ่งไม่ได้สร้างสตริงที่ถูกต้อง ผลลัพธ์ที่ได้คือ 1

แนวทางที่ใช้ในโปรแกรมด้านล่างมีดังนี้

• ป้อนอาร์เรย์สตริงของคำและคำนวณขนาดโดยใช้ฟังก์ชัน size()

• ประกาศตัวแปรเป็น min_val และตั้งค่าเป็น INT_MAX เป็นค่าสูงสุดที่เป็นไปได้

• สร้างวัตถุประเภทโครงสร้างเป็นรูทและตั้งค่าให้เรียกใช้ฟังก์ชัน Return_Node()

• เริ่มลูป FOR จาก i ถึง 0 จนถึงขนาดของอาร์เรย์ ภายในลูป ให้เรียกใช้ฟังก์ชัน Insert_Node() เพื่อแทรกโหนดในแผนผัง

• เรียก Minimum_Break() เพื่อคำนวณตัวแบ่งคำขั้นต่ำที่เป็นไปได้และพิมพ์ผลลัพธ์สุดท้าย

• ประกาศโครงสร้างเพื่อสร้าง tree of nodes โดยมีคำเป็นข้อมูล

  • สร้างอาร์เรย์ของพอยน์เตอร์เป็น ptr[total_Alpha] และตัวแปรบูลีนเป็นเช็ค

• ภายใน Return_Node(เป็นโมฆะ)

  • สร้างตัวชี้ของโครงสร้างประเภทเป็น ptr_1 ตั้งค่า ptr_1->ตรวจสอบว่าเป็นเท็จ

  • เริ่มวนรอบ FOR จาก i ถึง 0 จนถึง i น้อยกว่า total_Alpha ภายในลูป ให้ตั้งค่า ptr_1->ptr[i] เป็น NULL

  • กลับ ptr_1

• ภายในฟังก์ชัน Insert_Node(struct node* root, string val)

  • สร้างตัวชี้เป็น ptr_1 และตั้งค่าเป็นรูท

  • เริ่มวนรอบ FOR จาก i ถึง 0 จนถึง val.length() ภายในลูป ให้ตั้งค่าคีย์เป็น val[i] - 'a' และตรวจสอบว่า ptr_1->ptr[key] เป็น NULL แล้วตั้งค่า ptr_1->ptr[key] เป็นการเรียกใช้ฟังก์ชัน Return_Node()

  • ตั้งค่า ptr_1 เป็น ptr_1->ptr[key] และ ptr_1->ตรวจสอบเป็นจริง

• ภายในฟังก์ชัน Minimum_Break(struct node* root, string val, int first, int* temp, int a =0)

  • สร้างตัวชี้เป็น ptr_1 และตั้งค่าเป็นรูท

  • ตรวจสอบ IF first =val.length() จากนั้นตั้งค่า *temp เพื่อเรียกใช้ฟังก์ชัน inbuilt ของ C++ ซึ่งเป็นค่า min(*temp, a - 1) และส่งคืน

  • เริ่มวนรอบ FOR จาก i ถึงก่อน จนถึง i น้อยกว่าความยาวของวาล ภายในลูป ให้ตั้งค่าที่อยู่เป็น val[i] - 'a' และตรวจสอบว่า ptr_1->ptr[address] เป็นโมฆะแล้วส่งคืน

  • ตรวจสอบว่า ptr_1->ptr[address]->check เป็นจริง จากนั้นให้เรียก Minimum_Break(root, val, i + 1, temp, 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