数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济学
心理学
社会学
服装学
法学C++中的最小单词拆分问题
给定一个任意大小的单词字符串数组，任务是将单词以所有可能的方式拆分，使得拆分后的字符串是有效的字符串，并且我们必须根据问题计算所有此类最小单词拆分。
让我们看看这个问题的各种输入输出场景：
输入 - 字符串 word[] = {"Hello", "Hell", "tell", "well", "bell", "ball", "all" }
输出 - 最小单词拆分是：1
解释 - 给定多个单词。现在，我们将传递两个字符串（例如，Hell 和 all）的连接，并将连接的单词拆分。因此，Hellall 可以分为“Hell all”，这是第一次拆分，两个单词都是有效的。现在，我们将进一步拆分它，即“He ll aa”，这不会形成任何有效的字符串。因此，输出为 1。
输入 - 字符串 word[] = {"Hello", "Hell", "tell", "well", "bell", "ball", "all" }
输出 - 最小单词拆分是：1
解释 - 给定多个单词。现在，我们将传递两个字符串（例如，Hell 和 well）的连接，并将连接的单词拆分。因此，Hellwell 可以分为“Hell well”，这是第一次拆分，两个单词都是有效的。现在，我们将进一步拆分它，即“He ll well”，这不会形成任何有效的字符串。因此，输出为 1。
下面程序中使用的方法如下：
输入单词的字符串数组，并使用 size() 函数计算大小。
声明一个变量为 min_val 并将其设置为 INT_MAX 作为最大可能值。
创建一个结构体类型的对象作为 root 并将其设置为 Return_Node() 函数的调用。
从 i 为 0 开始循环到数组大小。在循环内，调用 Insert_Node() 函数以将节点插入树中。
调用 Minimum_Break() 来计算可能的最小单词拆分并打印最终结果。
声明一个结构体来构建具有单词作为数据的节点树。
创建一个指针数组 ptr[total_Alpha] 和一个布尔变量 check。
在 Return_Node(void) 内：
创建一个结构体类型的指针 ptr_1。将 ptr_1->check 设置为 false
从 i 为 0 开始循环到 i 小于 total_Alpha。在循环内，将 ptr_1->ptr[i] 设置为 NULL
返回 ptr_1
在函数 Insert_Node(struct node* root, string val) 内：
创建一个指针 ptr_1 并将其设置为 root。
从 i 为 0 开始循环到 val.length()。在循环内，将 key 设置为 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。
检查如果 first = val.length()，则将 *temp 设置为 C++ 的内置函数的调用，该函数为 min(*temp, a - 1) 并返回。
从 i 为 first 开始循环到 i 小于 val 的长度。在循环内，将 address 设置为 val[i] - 'a'，如果 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[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
219 次浏览
