Bài toán tách từ tối thiểu (Minimum Word Break) trong C++

Cho từ điển các từ. Tìm số lần tách nhỏ nhất để một chuỗi cho trước thành các từ hợp lệ trong từ điển.

Ví dụ

Từ điển: {"Hello", "Hell", "tell", "well", "bell", "ball", "all"}

Chuỗi: "Hellall" → Tách: "Hell all" (1 lần tách). Không tách được thêm → kết quả 1.

Chuỗi: "Hellwell" → "Hell well" (1 lần tách).

Phương pháp: Trie + DFS/Backtracking

• Xây Trie từ từ điển.
• Duyệt chuỗi, tại mỗi vị trí thử mở rộng trong Trie. Nếu gặp từ kết thúc (check=true) → đệ quy từ vị trí tiếp theo, tăng đếm tách.
• Cập nhật minimum toàn cục.

Ví dụ mã C++

#include <bits/stdc++.h>
using namespace std;
const int ALPHA = 26;

struct TrieNode {
    TrieNode* child[ALPHA];
    bool isEnd;
    TrieNode() { isEnd=false; fill(begin(child), end(child), nullptr); }
};

TrieNode* newNode() { return new TrieNode(); }

void insert(TrieNode* root, string s) {
    for (char c: s) {
        int idx = tolower(c) - 'a';
        if (!root->child[idx]) root->child[idx] = newNode();
        root = root->child[idx];
    }
    root->isEnd = true;
}

void minBreak(TrieNode* root, string &s, int pos, int &ans, int cuts=0) {
    if (pos == s.size()) { ans = min(ans, cuts); return; }
    TrieNode* cur = root;
    for (int i=pos; ichild[idx]) return;
        cur = cur->child[idx];
        if (cur->isEnd) minBreak(root, s, i+1, ans, cuts+1);
    }
}

int main() {
    string dict[] = {"Hello", "Hell", "tell", "well", "bell", "ball", "all"};
    TrieNode* root = newNode();
    for (auto &w: dict) insert(root, w);
    string s = "Hellall";
    int ans = INT_MAX;
    minBreak(root, s, 0, ans);
    cout << "Minimum Word Break: " << (ans==INT_MAX?-1:ans-1); // cuts = words-1
    return 0;
}

Đầu ra chương trình

Minimum Word Break is: 1