Synonymous Sentences

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52

#include <vector>
#include <string>
#include <unordered_map>
#include <set>
#include <algorithm>
using namespace std;
class Solution {
    unordered_map<string, string> parent;
    string find(string x) {
        if (parent.count(x) == 0) parent[x] = x;
        if (parent[x] != x) parent[x] = find(parent[x]);
        return parent[x];
    }
public:
    vector<string> generateSentences(vector<vector<string>>& synonyms, string text) {
        for (auto& p : synonyms) {
            parent[find(p[0])] = find(p[1]);
        }
        unordered_map<string, set<string>> groups;
        for (auto& p : synonyms) {
            string g = find(p[0]);
            groups[g].insert(p[0]);
            groups[g].insert(p[1]);
        }
        vector<string> words;
        string w;
        for (char c : text) {
            if (c == ' ') { words.push_back(w); w.clear(); }
            else w += c;
        }
        if (!w.empty()) words.push_back(w);
        vector<vector<string>> options;
        for (auto& word : words) {
            string g = find(word);
            if (groups.count(g)) {
                vector<string> v(groups[g].begin(), groups[g].end());
                sort(v.begin(), v.end());
                options.push_back(v);
            } else {
                options.push_back({word});
            }
        }
        vector<string> res;
        function<void(int, string)> dfs = [&](int i, string s) {
            if (i == options.size()) { res.push_back(s.substr(1)); return; }
            for (auto& w : options[i]) dfs(i+1, s + " " + w);
        };
        dfs(0, "");
        sort(res.begin(), res.end());
        return res;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46

import java.util.*;
class Solution {
    Map<String, String> parent = new HashMap<>();
    String find(String x) {
        if (!parent.containsKey(x)) parent.put(x, x);
        if (!parent.get(x).equals(x)) parent.put(x, find(parent.get(x)));
        return parent.get(x);
    }
    public List<String> generateSentences(List<List<String>> synonyms, String text) {
        for (List<String> p : synonyms) parent.put(find(p.get(0)), find(p.get(1)));
        Map<String, Set<String>> groups = new HashMap<>();
        for (List<String> p : synonyms) {
            String g = find(p.get(0));
            groups.computeIfAbsent(g, k -> new TreeSet<>()).add(p.get(0));
            groups.get(g).add(p.get(1));
        }
        String[] words = text.split(" ");
        List<List<String>> options = new ArrayList<>();
        for (String word : words) {
            String g = find(word);
            if (groups.containsKey(g)) {
                List<String> v = new ArrayList<>(groups.get(g));
                Collections.sort(v);
                options.add(v);
            } else {
                options.add(Arrays.asList(word));
            }
        }
        List<String> res = new ArrayList<>();
        dfs(options, 0, new StringBuilder(), res);
        Collections.sort(res);
        return res;
    }
    void dfs(List<List<String>> options, int i, StringBuilder sb, List<String> res) {
        if (i == options.size()) {
            res.add(sb.toString().trim());
            return;
        }
        for (String w : options.get(i)) {
            int len = sb.length();
            sb.append(" ").append(w);
            dfs(options, i+1, sb, res);
            sb.setLength(len);
        }
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

class Solution {
    fun generateSentences(synonyms: List<List<String>>, text: String): List<String> {
        val parent = mutableMapOf<String, String>()
        fun find(x: String): String {
            if (parent[x] == null) parent[x] = x
            if (parent[x] != x) parent[x] = find(parent[x]!!)
            return parent[x]!!
        }
        for (p in synonyms) parent[find(p[0])] = find(p[1])
        val groups = mutableMapOf<String, MutableSet<String>>()
        for (p in synonyms) {
            val g = find(p[0])
            groups.getOrPut(g) { sortedSetOf() }.add(p[0])
            groups[g]!!.add(p[1])
        }
        val words = text.split(" ")
        val options = words.map { word ->
            val g = find(word)
            if (groups.containsKey(g)) groups[g]!!.toList().sorted() else listOf(word)
        }
        val res = mutableListOf<String>()
        fun dfs(i: Int, sb: StringBuilder) {
            if (i == options.size) {
                res.add(sb.toString().trim())
                return
            }
            for (w in options[i]) {
                val len = sb.length
                sb.append(" ").append(w)
                dfs(i+1, sb)
                sb.setLength(len)
            }
        }
        dfs(0, StringBuilder())
        return res.sorted()
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

from collections import defaultdict
class Solution:
    def generateSentences(self, synonyms: list[list[str]], text: str) -> list[str]:
        parent = {}
        def find(x):
            if x not in parent: parent[x] = x
            if parent[x] != x: parent[x] = find(parent[x])
            return parent[x]
        for a, b in synonyms:
            parent[find(a)] = find(b)
        groups = defaultdict(set)
        for a, b in synonyms:
            g = find(a)
            groups[g].add(a)
            groups[g].add(b)
        words = text.split()
        options = []
        for word in words:
            g = find(word)
            if g in groups:
                options.append(sorted(groups[g]))
            else:
                options.append([word])
        res = []
        def dfs(i, path):
            if i == len(options):
                res.append(' '.join(path))
                return
            for w in options[i]:
                dfs(i+1, path + [w])
        dfs(0, [])
        return sorted(res)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47

use std::collections::{HashMap, BTreeSet};
impl Solution {
    pub fn generate_sentences(synonyms: Vec<Vec<String>>, text: String) -> Vec<String> {
        let mut parent = HashMap::new();
        fn find(x: &str, parent: &mut HashMap<String, String>) -> String {
            if !parent.contains_key(x) { parent.insert(x.to_string(), x.to_string()); }
            if parent[x] != x { let p = parent[x].clone(); parent.insert(x.to_string(), find(&p, parent)); }
            parent[x].clone()
        }
        for p in &synonyms {
            let a = find(&p[0], &mut parent);
            let b = find(&p[1], &mut parent);
            parent.insert(a, b);
        }
        let mut groups: HashMap<String, BTreeSet<String>> = HashMap::new();
        for p in &synonyms {
            let g = find(&p[0], &mut parent);
            groups.entry(g.clone()).or_default().insert(p[0].clone());
            groups.entry(g.clone()).or_default().insert(p[1].clone());
        }
        let words: Vec<&str> = text.split_whitespace().collect();
        let mut options: Vec<Vec<String>> = vec![];
        for word in &words {
            let g = find(word, &mut parent);
            if let Some(set) = groups.get(&g) {
                options.push(set.iter().cloned().collect());
            } else {
                options.push(vec![word.to_string()]);
            }
        }
        let mut res = vec![];
        fn dfs(i: usize, options: &Vec<Vec<String>>, path: Vec<String>, res: &mut Vec<String>) {
            if i == options.len() {
                res.push(path.join(" "));
                return;
            }
            for w in &options[i] {
                let mut new_path = path.clone();
                new_path.push(w.clone());
                dfs(i+1, options, new_path, res);
            }
        }
        dfs(0, &options, vec![], &mut res);
        res.sort();
        res
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

function generateSentences(synonyms: string[][], text: string): string[] {
    const parent: Record<string, string> = {};
    function find(x: string): string {
        if (!(x in parent)) parent[x] = x;
        if (parent[x] !== x) parent[x] = find(parent[x]);
        return parent[x];
    }
    for (const [a, b] of synonyms) parent[find(a)] = find(b);
    const groups: Record<string, Set<string>> = {};
    for (const [a, b] of synonyms) {
        const g = find(a);
        if (!(g in groups)) groups[g] = new Set();
        groups[g].add(a); groups[g].add(b);
    }
    const words = text.split(' ');
    const options: string[][] = words.map(word => {
        const g = find(word);
        if (g in groups) return Array.from(groups[g]).sort();
        return [word];
    });
    const res: string[] = [];
    function dfs(i: number, path: string[]) {
        if (i === options.length) {
            res.push(path.join(' '));
            return;
        }
        for (const w of options[i]) dfs(i+1, [...path, w]);
    }
    dfs(0, []);
    res.sort();
    return res;
}