Minimum Word Break Problem ใน C++

ได้รับอาร์เรย์สตริงคำศัพท์ หาจำนวนการแบ่งคำ (word break) น้อยที่สุด ที่ทำให้สตริงที่ต่อกัน (concatenated) แบ่งเป็นคำในพจนานุสรณีได้

ตัวอย่าง

Input: word[] = {"Hello", "Hell", "tell", "well", "bell", "ball", "all"}

Output: Minimum Word Break is: 1

คำอธิบาย: ตัวอย่าง "Hell" + "all" = "Hellall" → แบ่งได้ "Hell all" (1 break) แบ่งต่อ "He ll all" ไม่ได้คำถูกต้อง → คำตอบ 1

อัลกอริทึม: Trie + DFS/Recursion

• สร้าง Trie จากคำในพจนานุสรณี (Insert_Node)
• Minimum_Break(root, val, first, &temp, a) แบบ recursive:
  • ถ้า first == val.length() → อัปเดต temp = min(temp, a-1)
  • วน i = first ถึง len-1: ตรวจสอบ prefix ใน Trie
  • ถ้าเจอคำสมบูรณ์ (check == true) เรียกซ้ำจาก i+1 เพิ่ม a
• เริ่มต้น min_val = INT_MAX เรียก Minimum_Break(root, "Hellall", 0, &min_val, 0)

ตัวอย่างโค้ด C++

#include <bits/stdc++.h>
using namespace std;
#define total_Alpha 26

struct node {
    struct node* ptr[total_Alpha];
    bool check;
};

struct node* Return_Node() {
    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 << "Minimum Word Break is: " << min_val;
    return 0;
}

ผลลัพธ์

Minimum Word Break is: 1