C++의 최소 단어 분리 문제

주어진 크기의 단어 배열 문자열이 주어지고 작업은 가능한 모든 방법으로 단어를 끊는 것입니다. 중단 후에 형성된 문자열은 유효한 문자열이어야 하고 다음과 같이 모든 최소 단어 나누기를 계산해야 합니다. 문제.

이에 대한 다양한 입력 출력 시나리오를 살펴보겠습니다. -

에서 − 문자열 단어[] ={"안녕하세요", "지옥", "말해", "잘", "벨", "공", "모두" }

밖으로 − 최소 단어 구분:1

설명 - 우리는 여러 단어로 주어집니다. 이제 우리는 두 개의 문자열, 즉 지옥과 모든 것의 연결을 전달하고 연결된 단어를 끊을 것입니다. 따라서 Hellall은 첫 번째 break 인 "Hellall"로 나눌 수 있으며 두 단어가 모두 유효합니다. 이제 유효한 문자열을 형성하지 않는 "He lla a"와 같이 더 세분화하겠습니다. 따라서 출력은 1입니다.

에서 − 문자열 단어[] ={"안녕하세요", "지옥", "말해", "잘", "벨", "공", "모두" }

밖으로 − 최소 단어 구분:1

설명 - 우리는 여러 단어로 주어집니다. 이제 우리는 두 문자열, 즉 지옥과 우물의 연결을 전달하고 연결된 단어를 끊을 것입니다. 따라서 Hellwell은 첫 번째 break인 "Hell well"로 나눌 수 있으며 두 단어 모두 유효합니다. 이제 유효한 문자열을 형성하지 않는 "He ll well"을 더 깰 것입니다. 따라서 출력은 1입니다.

아래 프로그램에서 사용된 접근 방식은 다음과 같습니다.

• 단어의 문자열 배열을 입력하고 size() 함수를 사용하여 크기를 계산합니다.

• 변수를 min_val로 선언하고 가능한 최대값으로 INT_MAX로 설정합니다.

• 유형 구조의 객체를 루트로 생성하고 함수 Return_Node()

  에 대한 호출로 설정합니다.

• 배열의 크기까지 i에서 0까지 루프 FOR를 시작합니다. 루프 내에서 Insert_Node() 함수를 호출하여 트리에 노드를 삽입합니다.

• Minimum_Break()를 호출하여 가능한 최소 단어 나누기를 계산하고 최종 결과를 인쇄합니다.

• 단어를 데이터로 사용하여 노드 트리를 구성하는 구조를 선언합니다.

  • 포인터 배열을 ptr[total_Alpha]로 만들고 부울 변수를 검사로 만듭니다.

• Return_Node(void) 내부

  • 유형 구조의 포인터를 ptr_1로 만듭니다. ptr_1->거짓으로 확인

    설정

  • i에서 total_Alpha보다 작아질 때까지 루프 FOR를 시작합니다. 루프 내에서 ptr_1->ptr[i]를 NULL

    로 설정합니다.

  • ptr_1 반환

• Insert_Node(struct node* root, string val)

  함수 내부

  • 포인터를 ptr_1로 만들고 루트로 설정합니다.

  • val.length()까지 루프 FOR를 i에서 0으로 시작합니다. 루프 내에서 키를 val[i] - 'a'로 설정하고 ptr_1->ptr[key]가 NULL인지 확인한 다음 ptr_1->ptr[key]를 함수 Return_Node() 호출로 설정합니다.

  • ptr_1을 ptr_1->ptr[key]로 설정하고 ptr_1->true로 확인

    하십시오.

• 함수 내부에서 Minimum_Break(struct node* root, string val, int first, int* temp, int a =0)

  • 포인터를 ptr_1로 만들고 루트로 설정합니다.

  • 먼저 IF =val.length()를 확인한 다음 *temp를 설정하여 C++의 내장 함수인 min(*temp, a - 1)을 호출하고 반환합니다.

  • i에서 val 길이보다 작은 i까지 루프 FOR를 시작합니다. 루프 내에서 주소를 val[i] - 'a'로 설정하고 IF 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[주소]로 설정합니다.

예시

#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