C++中的最小分词问题

2026-06-03 1 花语

我们得到一个任意给定大小的单词数组字符串，任务是以所有可能的方式拆分单词，以便在拆分后形成的字符串应该是一个有效的字符串，我们必须根据问题。

让我们看看这个的各种输入输出场景-

在 -字符串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