Vấn đề ngắt từ tối thiểu trong C ++

Chúng tôi được cung cấp một chuỗi mảng gồm các từ có kích thước bất kỳ và nhiệm vụ là ngắt các từ theo tất cả các cách có thể sao cho sau khi ngắt, chuỗi được tạo thành phải là một chuỗi hợp lệ và chúng tôi phải tính toán tất cả các ngắt từ tối thiểu như vậy vấn đề.

Hãy cho chúng tôi xem các tình huống đầu ra đầu vào khác nhau cho việc này -

Trong - string word [] ={"Xin chào", "Địa ngục", "nói", "tốt", "chuông", "quả bóng", "tất cả"}

Hết - Ngắt từ Tối thiểu là:1

Giải thích - chúng tôi được đưa ra với nhiều từ. Bây giờ chúng ta sẽ chuyển đoạn nối của hai chuỗi tức là Hell và all và sẽ ngắt từ được nối. Vì vậy, Hellall có thể được chia thành “Hellall” là dấu ngắt đầu tiên và cả hai từ đều hợp lệ. Bây giờ, chúng ta sẽ phá vỡ nó hơn nữa, tức là “He ll aa” không tạo thành bất kỳ chuỗi hợp lệ nào. Vì vậy, đầu ra là 1.

Trong - string word [] ={"Xin chào", "Địa ngục", "nói", "tốt", "chuông", "quả bóng", "tất cả"}

Hết - Ngắt từ Tối thiểu là:1

Giải thích - chúng tôi được đưa ra với nhiều từ. Bây giờ chúng ta sẽ chuyển từ nối của hai chuỗi tức là Hell and well và sẽ ngắt từ được nối. Vì vậy, Hellwell có thể được chia thành “Giếng địa ngục” là lần nghỉ đầu tiên và cả hai từ đều hợp lệ. Bây giờ, chúng ta sẽ phá vỡ nó hơn nữa, tức là "Anh ấy sẽ tốt" không tạo thành bất kỳ chuỗi hợp lệ nào. Vì vậy, đầu ra là 1.

Phương pháp tiếp cận được sử dụng trong chương trình dưới đây như sau

• Nhập mảng chuỗi từ và tính kích thước bằng cách sử dụng hàm size ().

• Khai báo một biến là min_val và đặt nó thành INT_MAX là giá trị lớn nhất có thể.

• Tạo một đối tượng có cấu trúc kiểu làm gốc và đặt nó thành lệnh gọi hàm Return_Node ()

• Bắt đầu vòng lặp FOR từ i đến 0 cho đến hết kích thước của một mảng. Bên trong vòng lặp, hãy gọi hàm Insert_Node () để chèn nút vào một cây.

• Gọi Minimum_Break () để tính toán ngắt từ tối thiểu có thể và in kết quả cuối cùng.

• Khai báo một cấu trúc để xây dựng cây các nút với các từ là dữ liệu.

  • Tạo một mảng con trỏ dưới dạng ptr [total_Alpha] và một biến boolean dưới dạng kiểm tra.

• Bên trong Return_Node (void)

  • Tạo một con trỏ có kiểu cấu trúc là ptr_1. Đặt ptr_1-> kiểm tra là false

  • Bắt đầu lặp FOR từ i đến 0 cho đến khi tôi nhỏ hơn total_Alpha. Bên trong vòng lặp, đặt ptr_1-> ptr [i] thành NULL

  • Trả lại ptr_1

• Bên trong hàm Insert_Node (struct node * root, string val)

  • Tạo một con trỏ dưới dạng ptr_1 và đặt nó thành root.

  • Bắt đầu vòng lặp FOR từ i đến 0 cho đến val.length (). Bên trong vòng lặp, đặt khóa là val [i] - ‘a’ và kiểm tra IF ptr_1-> ptr [key] là NULL, sau đó đặt ptr_1-> ptr [key] thành lệnh gọi của hàm Return_Node ().

  • Đặt ptr_1 thành ptr_1-> ptr [key] và ptr_1-> kiểm tra thành true

• Bên trong hàm Minimum_Break (struct node * root, string val, int first, int * temp, int a =0)

  • Tạo một con trỏ dưới dạng ptr_1 và đặt nó thành root.

  • Kiểm tra IF đầu tiên =val.length (), sau đó đặt * temp để gọi hàm có sẵn của C ++ là min (* temp, a - 1) và trả về.

  • Bắt đầu vòng lặp FOR từ tôi đến đầu tiên cho đến khi tôi nhỏ hơn chiều dài của một val. Bên trong vòng lặp, đặt địa chỉ là val [i] - 'a' và kiểm tra NẾU ptr_1-> ptr [address] là null thì trả về.

  • Kiểm tra IF ptr_1-> ptr [address] -> kiểm tra là true rồi gọi Minimum_Break (root, val, i + 1, temp, a + 1)

  • Đặt ptr_1 thành ptr_1-> ptr [address].

Ví dụ

#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;
}

Đầu ra

Nếu chúng ta chạy đoạn mã trên, nó sẽ tạo ra Kết quả sau

Minimum Word Break is: 1