README_EN.md

1258. Synonymous Sentences

中文文档

Description

Given a list of pairs of equivalent words synonyms and a sentence text, Return all possible synonymous sentences sorted lexicographically.

 

Example 1:

Input:
synonyms = [["happy","joy"],["sad","sorrow"],["joy","cheerful"]],
text = "I am happy today but was sad yesterday"
Output:
["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"]

Example 2:

Input: synonyms = [["happy","joy"],["cheerful","glad"]], text = "I am happy today but was sad yesterday"
Output: ["I am happy today but was sad yesterday","I am joy today but was sad yesterday"]

Example 3:

Input: synonyms = [["a","b"],["c","d"],["e","f"]], text = "a c e"
Output: ["a c e","a c f","a d e","a d f","b c e","b c f","b d e","b d f"]

Example 4:

Input: synonyms = [["a","QrbCl"]], text = "d QrbCl ya ya NjZQ"
Output: ["d QrbCl ya ya NjZQ","d a ya ya NjZQ"]

 

Constraints:

• 0 <= synonyms.length <= 10
• synonyms[i].length == 2
• synonyms[i][0] != synonyms[i][1]
• All words consist of at most 10 English letters only.
• text is a single space separated sentence of at most 10 words.

Solutions

Python3

class Solution:
    def generateSentences(self, synonyms: List[List[str]], text: str) -> List[str]:
        p = {}

        def find(x):
            if p[x] != x:
                p[x] = find(p[x])
            return p[x]

        for a, b in synonyms:
            p[a] = a
            p[b] = b
        for a, b in synonyms:
            p[find(a)] = find(b)

        s = collections.defaultdict(set)
        for a, b in synonyms:
            s[find(a)].add(a)
            s[find(b)].add(b)
        res = []
        for word in text.split(' '):
            if word not in p:
                if not res:
                    res.append([word])
                else:
                    for a in res:
                        a.append(word)
            else:
                words = sorted(s[find(word)])
                if not res:
                    for b in words:
                        res.append([b])
                else:
                    res = [a + [b] for a in res for b in words]
        return [' '.join(sentence) for sentence in res]

Java

class Solution {
    private Map<String, String> p;

    public List<String> generateSentences(List<List<String>> synonyms, String text) {
        p = new HashMap<>();
        for (List<String> item : synonyms) {
            p.put(item.get(0), item.get(0));
            p.put(item.get(1), item.get(1));
        }
        for (List<String> item : synonyms) {
            p.put(find(item.get(0)), find(item.get(1)));
        }
        Map<String, Set<String>> s = new HashMap<>();
        for (List<String> item : synonyms) {
            String a = find(item.get(0)), b = find(item.get(1));
            if (!s.containsKey(a)) {
                s.put(a, new HashSet<>());
            }
            if (!s.containsKey(b)) {
                s.put(b, new HashSet<>());
            }
            s.get(a).add(item.get(0));
            s.get(b).add(item.get(1));
        }
        List<List<String>> all = new ArrayList<>();
        for (String word : text.split(" ")) {
            if (!p.containsKey(word)) {
                if (all.isEmpty()) {
                    List<String> t = new ArrayList<>();
                    t.add(word);
                    all.add(t);
                } else {
                    for (List<String> a : all) {
                        a.add(word);
                    }
                }
            } else {
                Set<String> words = s.get(find(word));
                if (all.isEmpty()) {
                    for (String b : words) {
                        List<String> t = new ArrayList<>();
                        t.add(b);
                        all.add(t);
                    }
                } else {
                    List<List<String>> t = new ArrayList<>();
                    for (List<String> a : all) {
                        for (String b : words) {
                            List<String> c = new ArrayList<>(a);
                            c.add(b);
                            t.add(c);
                        }
                    }
                    all = t;
                }
            }
        }
        List<String> res = new ArrayList<>();
        for (List<String> item : all) {
            res.add(String.join(" ", item));
        }
        Collections.sort(res);
        return res;
    }

    private String find(String x) {
        if (!Objects.equals(p.get(x), x)) {
            p.put(x, find(p.get(x)));
        }
        return p.get(x);
    }
}

...