Question

Formatted question description: https://leetcode.ca/all/1258.html

 1258. Synonymous Sentences

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


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

Algorithm

Union search, recursive enumeration

  • O(2^n⋅L)

Use the union search to find the synonym group, and then recursively enumerate and replace the synonym.

Time complexity

The total time complexity of finding the synonym group is approximately O(n), and the time complexity of recursion is O(2^n *L), where L is the length of the string O(L) time is required for each word replacement).

Therefore, the total time complexity is O(2^n *L).

Space complexity

Union search requires O(n) space, and recording answers requires O(2&n *L) space, so the total space complexity is O(2^n *L).

Code

Java

public class Synonymous_Sentences {

    class Solution {

        // word => its similar words set
        Map<String, Set<String>> map = new HashMap<>();
        List<String> res = new ArrayList<>();

        public List<String> generateSentences(List<List<String>> synonyms, String text) {

            //build graph.
            for (List<String> s : synonyms) {
                String a = s.get(0);
                String b = s.get(1);
                map.getOrDefault(a, new HashSet<>()).add(b);
                map.getOrDefault(b, new HashSet<>()).add(a);
            }

            String[] split = text.split("\\W+");
            helper(split, 0, "");

            Collections.sort(res);
            return res;
        }

        public void helper(String[] wordsArray, int index, String cur) {

            if (index == wordsArray.length) {
                res.add(cur);
                return;
            }

            if (map.containsKey(wordsArray[index])) {
                List<String> choices = new ArrayList<>();
                //find all synonyms related to s
                getSynonyms(wordsArray[index], new HashSet<>(), choices);

                //try to change word at index to every possible synonyms word
                for (String s : choices) {
                    helper(wordsArray, index + 1, cur + (index == wordsArray.length - 1 ? s : s + " "));
                }
            } else {
                //if the word at index has no synonyms, just go for next.
                helper(wordsArray, index + 1, cur + (index == wordsArray.length - 1 ? wordsArray[index] : wordsArray[index] + " "));
            }
        }

        //get all synonyms related to s
        public void getSynonyms(String s, Set<String> visited, List<String> choices) {
            choices.add(s);
            visited.add(s);
            for (String each : map.get(s)) {
                if (!visited.contains(each)) {
                    getSynonyms(each, visited, choices);
                }
            }
        }
    }
}

All Problems

All Solutions