C++での最小の単語区切りの問題

任意のサイズの単語の配列文字列が与えられます。タスクは、可能なすべての方法で単語を分割することです。これにより、分割後に形成される文字列が有効な文字列になり、そのような最小の単語分割をすべて計算する必要があります。問題。

このためのさまざまな入出力シナリオを見てみましょう-

で − string word [] ={"Hello"、 "Hell"、 "tell"、 "well"、 "bell"、 "ball"、 "all"}

アウト −最小単語区切りは次のとおりです：1

説明 −私たちは複数の言葉を与えられています。次に、2つの文字列の連結、つまり地獄とすべてを渡し、連結された単語を分割します。したがって、Hellallは最初の休憩である「Hellall」として分割でき、両方の単語が有効です。ここで、それをさらに分割します。つまり、有効な文字列を形成していない「Hellaa」です。したがって、出力は1です。

で − string word [] ={"Hello"、 "Hell"、 "tell"、 "well"、 "bell"、 "ball"、 "all"}

アウト −最小単語区切りは次のとおりです：1

説明 −私たちは複数の言葉を与えられています。次に、2つの文字列の連結を渡します。つまり、地獄とよく、連結された単語を分割します。したがって、ヘルウェルは最初の休憩である「ヘルウェル」として分割することができ、両方の単語が有効です。ここで、それをさらに分割します。つまり、有効な文字列を形成していない「Hellwell」です。したがって、出力は1です。

以下のプログラムで使用されているアプローチは次のとおりです

• 単語の文字列配列を入力し、size（）関数を使用してサイズを計算します。

• 変数をmin_valとして宣言し、可能な最大値としてINT_MAXに設定します。

• rootとして構造型のオブジェクトを作成し、それを関数Return_Node（）

  の呼び出しに設定します。

• 配列のサイズまで、iから0までのループFORを開始します。ループ内で、関数Insert_Node（）を呼び出して、ノードをツリーに挿入します。

• Minimum_Break（）を呼び出して、可能な最小の単語区切りを計算し、最終結果を出力します。

• 単語をデータとしてノードのツリーを構築するための構造を宣言します。

  • ポインタの配列をptr[total_Alpha]として作成し、ブール変数をチェックとして作成します。

• Return_Node（void）の内部

  • タイプ構造のポインタをptr_1として作成します。 ptr_1->チェックをfalseに設定

  • iからtotal_Alpha未満になるまでループFORを開始します。ループ内で、ptr_1->ptr[i]をNULLに設定します

  • ptr_1を返す

• 関数Insert_Node（struct node * root、string val）

  の内部

  • ptr_1としてポインタを作成し、rootに設定します。

  • val.length（）までiから0までのループFORを開始します。ループ内で、キーを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に設定します。

  • IF first =val.length（）を確認してから、* tempを設定して、min（* temp、a -1）であるC++の組み込み関数を呼び出して返します。

  • iから最初のループFORを開始し、iがvalの長さ未満になるまで続けます。ループ内で、アドレスをval [i]-'a'として設定し、ptr_1-> ptr [address]がnullであることを確認してから、戻ります。

  • チェックIFptr_1->ptr [address]->チェックが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
//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