Задача: 1258. Synonymous Sentences
Сложность: medium

Вам дан список эквивалентных пар строк synonyms, где synonyms[i] = [si, ti] означает, что si и ti являются эквивалентными строками. Вам также дан текст предложения. Верните все возможные синонимичные предложения, отсортированные лексикографически.

Пример:

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"]

👨‍💻 Алгоритм:

1⃣Построить граф синонимов, используя структуру данных, такую как Union-Find или просто с использованием DFS/BFS.

2⃣Пройти по каждому слову в предложении и найти все возможные синонимы.
Сгенерировать все возможные комбинации предложений.

3⃣Отсортировать полученные предложения лексикографически.

😎 Решение:

import java.util.*;

public class Solution {
    public List<String> generateSentences(List<List<String>> synonyms, String text) {
        Map<String, Set<String>> graph = new HashMap<>();
        for (List<String> pair : synonyms) {
            graph.computeIfAbsent(pair.get(0), k -> new HashSet<>()).add(pair.get(1));
            graph.computeIfAbsent(pair.get(1), k -> new HashSet<>()).add(pair.get(0));
        }

        List<String> words = Arrays.asList(text.split(" "));
        List<List<String>> synonymGroups = new ArrayList<>();
        for (String word : words) {
            synonymGroups.add(new ArrayList<>(findSynonyms(graph, word)));
        }

        List<String> sentences = new ArrayList<>();
        generate(sentences, synonymGroups, new StringBuilder(), 0);
        Collections.sort(sentences);
        return sentences;
    }

    private Set<String> findSynonyms(Map<String, Set<String>> graph, String word) {
        Set<String> synonyms = new HashSet<>();
        Stack<String> stack = new Stack<>();
        stack.push(word);
        while (!stack.isEmpty()) {
            String w = stack.pop();
            if (synonyms.add(w)) {
                stack.addAll(graph.getOrDefault(w, Collections.emptySet()));
            }
        }
        return synonyms;
    }

    private void generate(List<String> sentences, List<List<String>> groups, StringBuilder sentence, int index) {
        if (index == groups.size()) {
            sentences.add(sentence.toString().trim());
            return;
        }
        int len = sentence.length();
        for (String word : groups.get(index)) {
            sentence.append(" ").append(word);
            generate(sentences, groups, sentence, index + 1);
            sentence.setLength(len);
        }
    }
}

Ставь 👍 и забирай 📚 Базу знаний