我们得到一个任意给定大小的单词数组字符串，任务是以所有可能的方式拆分单词，以便在拆分后形成的字符串应该是一个有效的字符串，我们必须根据问题。
让我们看看这个的各种输入输出场景 -
在 - 字符串 word[] = {"Hello", "Hell", "tell", "well", "bell", "ball", "all" }
Out - 最小分词为：1
说明 - 我们给出了多个单词。现在我们将传递两个字符串的连接，即 Hell 和 all 并将打破连接的单词。因此，Hellall 可分为“Hell all”，即初破，这两个词都有效。现在，我们将进一步打破它，即“He ll aa”，它没有形成任何有效的字符串。所以输出为1。
在 - 字符串 word[] = {"Hello", "Hell", "tell", "well", "bell", "ball", "all" }
Out - 最小分词为：1
说明 - 我们给出了多个单词。现在我们将传递两个字符串的连接，即 Hell 和 well 并将打破连接的单词。所以，Hellwell 可分为“Hell well”，即初破，这两个词都有效。现在，我们将进一步打破它，即“He ll well”，它没有形成任何有效的字符串。所以输出为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(struct node* root, string val) 中
创建一个指针为 ptr_1 并将其设置为 root。
从 i 到 0 开始循环 FOR 直到. 在循环内，将 key 设置为 val[i] - 'a' 并检查 IF ptr_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(struct node* root, string val, int first, int* temp, int a = 0)
创建一个指针为 ptr_1 并将其设置为 root。
首先检查 IF =然后设置 *temp 以调用 C++ 的内置函数 min(*temp, a - 1) 并返回。val.length()
从 i 到第一个循环 FOR，直到 i 小于 val 的长度。在循环内，将地址设置为 val[i] - 'a' 并检查 IF ptr_1->ptr[address] 是否为空然后返回。
检查 IF ptr_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