C++中的最小分词问题
我们得到一个任意给定大小的单词数组字符串，任务是以所有可能的方式拆分单词，以便在拆分后形成的字符串应该是一个有效的字符串，我们必须根据问题。
让我们看看这个的各种输入输出场景-
在 -字符串word[]={"Hello","Hell","tell","well","bell","ball","all"}
Out -最小分词为：1
说明 -我们给出了多个单词。现在我们将传递两个字符串的连接，即Hell和all并将打破连接的单词。因此，Hellall可分为“Hellall”，即初破，这两个词都有效。现在，我们将进一步打破它，即“Hellaa”，它没有形成任何有效的字符串。所以输出为1。
在 -字符串word[]={"Hello","Hell","tell","well","bell","ball","all"}
Out -最小分词为：1
说明 -我们给出了多个单词。现在我们将传递两个字符串的连接，即Hell和well并将打破连接的单词。所以，Hellwell可分为“Hellwell”，即初破，这两个词都有效。现在，我们将进一步打破它，即“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->check设置为false
从i到0开始循环FOR，直到i小于total_Alpha。在循环内，将ptr_1->ptr[i]设置为NULL
返回ptr_1
在函数Insert_Node(structnode*root,stringval)中
创建一个指针为ptr_1并将其设置为root。
从i到0开始循环FOR直到.在循环内，将key设置为val[i]-'a'并检查IFptr_1->ptr[key]为NULL然后将ptr_1->ptr[key]设置为function的调用。val.length()Return_Node()
将ptr_1设置为ptr_1->ptr[key]并将ptr_1->check设置为true
在函数内Minimum_Break(structnode*root,stringval,intfirst,int*temp,inta=0)
创建一个指针为ptr_1并将其设置为root。
首先检查IF=然后设置*temp以调用C++的内置函数min(*temp,a-1)并返回。val.length()
从i到第一个循环FOR，直到i小于val的长度。在循环内，将地址设置为val[i]-'a'并检查IFptr_1->ptr[address]是否为空然后返回。
检查IFptr_1->ptr[address]->check是否为真，然后调用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
//创建一个单词节点树
struct node{
struct node* ptr[total_Alpha];
bool check;
};
//返回包含所有节点的树
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;
}
//向树中的节点插入值
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;
}
//计算最小分词
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<<"最小断字为： "<< min_val;
return 0;
}输出结果如果我们运行上面的代码，它将生成以下输出
最小断字为： 1