ประโยคที่มีความหมายเหมือนกันใน C++

สมมติว่าเรามีรายการคู่คำที่มีความหมายเท่ากัน (synonyms) และประโยค text เราต้องหาประโยคที่เป็นไปได้ทั้งหมดที่มีความหมายเหมือนกัน เรียงตามลำดับ dictionary

ตัวอย่าง: synonyms = [["happy","joy"],["sad","sorrow"],["joy","cheerful"]], text = "I am happy today but was sad yesterday" ผลลัพธ์: 6 ประโยค

วิธีแก้ปัญหา

1. ใช้ Union-Find (Disjoint Set) จัดกลุ่มคำที่ synonymous
2. แยกประโยคเป็นคำๆ
3. ใช้ DFS สร้างประโยคทั้งหมด:
   • ถ้าคำไม่อยู่ในกลุ่ม synonym ใช้คำนั้น
   • ถ้าอยู่ในกลุ่ม ลองทุกคำในกลุ่มนั้น
4. เรียงผลลัพธ์และคืนค่า

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

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

void print_vector(vector<string> v){ 
    cout << "["; 
    for(int i = 0; i<v.size(); i++){ 
        cout << v[i] << ", "; 
    } 
    cout << "]"<<endl; 
} 

class Solution { 
public: 
    map<string, string> parent; 
    map<string, int> color; 
    map<int, set<string>> groupByColor; 
    
    string find(string s){ 
        if(parent[s] == s) return s; 
        parent[s] = find(parent[s]); 
        return parent[s]; 
    } 
    
    void unionNode(string a, string b){ 
        string x = find(a); 
        string y = find(b); 
        if(x == y) return; 
        parent[x] = y; 
    } 
    
    vector<string> ans; 
    
    vector<string> getString(string t){ 
        vector<string> temp; 
        string curr = ""; 
        for(char c : t){ 
            if(c == ' '){ 
                temp.push_back(curr); 
                curr = ""; 
            } else { 
                curr += c; 
            } 
        } 
        temp.push_back(curr); 
        return temp; 
    } 
    
    void dfs(vector<string>& strings, int idx, string temp = ""){ 
        if(idx == strings.size()){ 
            ans.push_back(temp); 
            return; 
        } 
        string current = strings[idx]; 
        if(color.find(current) == color.end()){ 
            dfs(strings, idx + 1, temp + current + (idx+1 == strings.size()?"":" ")); 
        } else { 
            set<string> x = groupByColor[color[current]]; 
            for(auto& z : x){ 
                dfs(strings, idx + 1, temp + z + (idx+1 == strings.size()?"":" ")); 
            } 
        } 
    } 
    
    vector<string> generateSentences(vector<vector<string>>& s, string t) { 
        int n = s.size(); 
        for(int i = 0; i < n; i++){ 
            string x = s[i][0], y = s[i][1]; 
            if(parent.find(x) == parent.end()) parent[x] = x; 
            if(parent.find(y) == parent.end()) parent[y] = y; 
            unionNode(x,y); 
        } 
        int c = 1; 
        for(int i = 0; i < n; i++){ 
            string x = s[i][0], z = s[i][1]; 
            string y = find(x); 
            if(color.find(y) == color.end()){ 
                color[y] = c++; 
            } 
            color[x] = color[y]; 
            color[z] = color[y]; 
            if(groupByColor.find(color[x]) == groupByColor.end()){ 
                set<string> ss; 
                ss.insert(x); ss.insert(y); 
                groupByColor[color[x]] = ss; 
            } else { 
                groupByColor[color[x]].insert(x); 
                groupByColor[color[x]].insert(z); 
            } 
        } 
        vector<string> strings = getString(t); 
        dfs(strings, 0); 
        sort(ans.begin(), ans.end()); 
        return ans; 
    } 
}; 

int main(){ 
    Solution ob; 
    vector<vector<string>> v = {{"happy","joy"},{"sad","sorrow"},{"joy","cheerful"}}; 
    print_vector(ob.generateSentences(v, "I am happy today but was sad yesterday")); 
}

ข้อมูลนำเข้า

[["happy","joy"],["sad","sorrow"],["joy","cheerful"]] "I am happy today but was sad yesterday"

ผลลัพธ์

[I am cheerful today but was sad yesterday, I am cheerful today but was sorrow yesterday, I am happy today but was sad yesterday, I am happy today but was sorrow yesterday, I am joy today but was sad yesterday, I am joy today but was sorrow yesterday, ]