Các câu đồng nghĩa (Synonymous Sentences) trong C++

Cho danh sách các cặp từ đồng nghĩa synonyms và một câu text. Tìm tất cả các câu đồng nghĩa có thể tạo ra bằng cách thay thế từ trong câu bằng từ đồng nghĩa của nó (bao gồm cả đồng nghĩa gián tiếp). Kết quả sắp xếp theo thứ tự từ điển.

Ví dụ

Đầu vào: synonyms = [["happy","joy"],["sad","sorrow"],["joy","cheerful"]], text = "I am happy today but was sad yesterday"
Đầu ra: 6 câu (xem chi tiết trong code).

Thuật toán: Union-Find + DFS

1. Union-Find (DSU): Gom nhóm các từ đồng nghĩa thành các thành phần liên thông.
2. Gom nhóm theo màu: Gán ID nhóm (color) cho mỗi gốc DSU, thu thập tất cả từ trong nhóm vào set (tự động sắp xếp).
3. DFS sinh câu: Tách câu thành mảng từ. Duyệt từng vị trí:
   • Nếu từ không có đồng nghĩa: giữ nguyên, đệ quy vị trí tiếp theo.
   • Nếu có: thử từng từ trong nhóm đồng nghĩa (đã sắp xếp), đệ quy.
4. Sắp xếp kết quả cuối cùng (dù DFS theo thứ tự từ điển đã cho kết quả gần như sắp xếp).

Triển khai C++

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

class Solution {
    map<string, string> parent;
    map<string, int> color;
    map<int, set<string>> groupByColor;
    vector<string> ans;

    string find(string s) {
        return parent[s] == s ? s : parent[s] = find(parent[s]);
    }
    void unite(string a, string b) {
        a = find(a); b = find(b);
        if (a != b) parent[a] = b;
    }
    vector<string> split(const string& s) {
        vector<string> res; string cur;
        for (char c : s) {
            if (c == ' ') { res.push_back(cur); cur = ""; }
            else cur += c;
        }
        res.push_back(cur);
        return res;
    }
    void dfs(const vector<string>& words, int idx, string cur) {
        if (idx == words.size()) { ans.push_back(cur); return; }
        const string& w = words[idx];
        if (!color.count(w)) {
            dfs(words, idx+1, cur + w + (idx+1==words.size()?"":" "));
        } else {
            for (const string& syn : groupByColor[color[w]]) {
                dfs(words, idx+1, cur + syn + (idx+1==words.size()?"":" "));
            }
        }
    }
public:
    vector<string> generateSentences(vector<vector<string>>& synonyms, string text) {
        // Build DSU
        for (auto& p : synonyms) {
            if (!parent.count(p[0])) parent[p[0]] = p[0];
            if (!parent.count(p[1])) parent[p[1]] = p[1];
            unite(p[0], p[1]);
        }
        // Assign colors & groups
        int c = 1;
        for (auto& p : synonyms) {
            string root = find(p[0]);
            if (!color.count(root)) color[root] = c++;
            color[p[0]] = color[p[1]] = color[root];
            groupByColor[color[root]].insert(p[0]);
            groupByColor[color[root]].insert(p[1]);
        }
        // Generate
        dfs(split(text), 0, "");
        sort(ans.begin(), ans.end());
        return ans;
    }
};

Độ phức tạp

• Thời gian: O(S α(S) + P * L) với S số từ đồng nghĩa, P số câu sinh ra, L độ dài câu.
• Không gian: O(S + P * L).

Kết quả kiểm thử

Đầu vào: [[happy,joy],[sad,sorrow],[joy,cheerful]], "I am happy today but was sad yesterday"
Đầu ra: 6 câu theo thứ tự từ điển.