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

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.

The problem can be solved using BFS. Consider the following input for simplicity:

Example Input:

synonyms = [[“happy”,”joy”],[“strong”,”healthy”],[“joy”,”cheerful”]],

text = “I am happy and strong”

This solution represented as pictorially:

BFS to generate Synonymous Sentences

  • We are creating a bidirectional graph from the synonyms. If happy and joy are synonym then the edge will look like the following :
    • happy --> joy
    • joy --> happy
  • We will add the original text in a queue and will continue until the queue is empty.
  • Get the text from the front of the queue and replace every word with its synonym. The synonymous words can be found in the graph that we have created earlier.
  • Add each of the resulting sentences in the resultset.
  • We are using a TreeSet to hold the results as the results need to be sorted in lexicographical order. 
class Solution {
    public List<String> generateSentences(List<List<String>> synonyms, String text) {
        
        Map<String, List<String>> graph = createGraph(synonyms);
        Queue<String> queue = new LinkedList<>();
        queue.offer(text);
        Set<String> result = new TreeSet<>();
        while(!queue.isEmpty()){
            String cur_text = queue.poll();
            result.add(cur_text);
            String[] words = cur_text.split(" ");
            for(int i = 0 ; i < words.length ; i++){
                String cur_word = words[i];
                if(!graph.containsKey(cur_word)){
                    continue;
                }
                List<String> synonymList = graph.get(cur_word);
                for(String synonym : synonymList){
                    words[i] = synonym;
                    String new_sentence = String.join(" ", words);
                    if(!result.contains(new_sentence)){
                        result.add(new_sentence);
                        queue.offer(new_sentence);
                    }
                }
            }
        }
        return new ArrayList<>(result);
    }
    
    private Map<String, List<String>> createGraph(List<List<String>> synonyms){
        Map<String, List<String>> graph = new HashMap<>();
        for(List<String> list : synonyms){
            String source = list.get(0);
            String destination = list.get(1);
            connect(graph, source, destination);
            connect(graph, destination, source);
        }
        return graph;
    }
    
    private void connect(Map<String, List<String>> graph, String source, 
                         String destination){
        List<String> adjacencyList = graph.get(source);
        if(adjacencyList == null){
            adjacencyList = new ArrayList<>();
            graph.put(source, adjacencyList);
        }
        adjacencyList.add(destination);
    }
}

Time: O(nm), where n is the number of words in the text, and m is the number of synonyms. This is because the text is split into word, O(n). In the worst case a word in the text has m synonyms.

Categories: BFS

Tagged as:

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s