資料結構
網路
關係資料庫管理系統 (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 次瀏覽
