Problem Explanation

This problem is asking to check whether given two sentences are similar or not. A word from one sentence is defined as similar to the corresponding word in the other sentence if the two words are identical or if the two words have been listed as similar pairs.

A sentence is only considered similar to another if both have the exact number of words.

Example

Given two sentences words1 = ["great", "acting", "skills"] and words2 = ["fine", "drama", "talent"] and pairs = [["great", "fine"], ["acting","drama"], ["skills","talent"]], the function should return True because the similarity between words1 and words2 is true for all 3 pairs.

Solution Approach

To solve this problem, the idea of using a hash table is applicable. We iterate through each of the pairs in the pairs list and then we map each word to its similar words. Finally, we check if the words in both sentences have been listed as a similar pair, or if they are the identical. If one pair does not meet either of the conditions, we return False, otherwise, we return True.

Let's apply this approach to our example. Our algorithm will execute the following steps:

1. For pairs = [["great", "fine"], ["acting","drama"], ["skills","talent"]], we map each word in pairs to its similar pair. Our map will look as follows:

   1
   2
   3{
   4'great' : {'fine'},
   5'fine' : {'great'},
   6'acting' : {'drama'},
   7'drama' : {'acting'},
   8'skills' : {'talent'},
   9'talent' : {'skills'}
   10}

2. Loop through all words in sentence1 and sentence2 respectively, let say word1 and word2:

For instance, words1 = ["great", "acting", "skills"] and words2 = ["fine", "drama", "talent"].

Compare 'great' and 'fine', both words are similar because 'fine' exists in the map of 'great'. Next, compare 'acting' and 'drama', both words are similar. Lastly, compare 'skills' and 'talent', both words are also similar.

3. If all the corresponding words are similar, return True otherwise False.

Python Solution

1
2python
3class Solution:
4    def areSentencesSimilar(self, words1, words2, pairs):
5        if len(words1) != len(words2):
6            return False
7        
8        words_map = {word: set() for pair in pairs for word in pair}
9        
10        for word1, word2 in pairs:
11            words_map[word1].add(word2)
12            words_map[word2].add(word1)
13            
14        return all(word1 == word2 or word1 in words_map and word2 in words_map[word1] for word1, word2 in zip(words1, words2))

Java Solution

1
2java
3class Solution {
4    public boolean areSentencesSimilar(String[] words1, String[] words2, List<List<String>> pairs) {
5        if (words1.length != words2.length) {
6            return false;
7        }
8        
9        HashMap<String, HashSet<String>> map = new HashMap<String, HashSet<String>>();
10        for (List<String> pair : pairs) {
11            map.putIfAbsent(pair.get(0), new HashSet<String>());
12            map.putIfAbsent(pair.get(1), new HashSet<String>());
13            map.get(pair.get(0)).add(pair.get(1));
14            map.get(pair.get(1)).add(pair.get(0));
15        }
16        
17        for (int i = 0; i < words1.length; i++) {
18            if (words1[i].equals(words2[i])) continue;
19            if (!map.containsKey(words1[i])) return false;
20            if (!map.get(words1[i]).contains(words2[i])) return false;
21        }
22        
23        return true;
24    }
25}

Javascript Solution

1
2javascript
3var areSentencesSimilar = function(words1, words2, pairs) {
4    if(words1.length != words2.length) return false;
5    
6    let map = new Map();
7    
8    for(let i = 0; i < pairs.length; i++){
9        if(!map.has(pairs[i][0])){
10            map.set(pairs[i][0], new Set());
11        }
12        
13        if(!map.has(pairs[i][1])){
14            map.set(pairs[i][1], new Set());
15        }
16        
17        map.get(pairs[i][0]).add(pairs[i][1]);
18        map.get(pairs[i][1]).add(pairs[i][0]);
19    }
20    
21    for(let i = 0; i < words1.length; i++){
22        if(words1[i] == words2[i]) continue;
23        
24        let set1 = map.get(words1[i]);
25        let set2 = map.get(words2[i]);
26        
27        if(!set1 && !set2) return false;
28        
29        if(set1 && !set1.has(words2[i]) || set2 && !set2.has(words1[i])) return false;
30    }
31    
32    return true;
33};

C++ Solution

1
2cpp
3class Solution {
4public:
5    bool areSentencesSimilar(vector<string>& words1, vector<string>& words2, vector<pair<string, string>>& pairs) {
6        if(words1.size()!=words2.size()) return false;
7        map<string, set<string>> m;
8        for(auto a:pairs){
9            m[a.first].insert(a.second);
10            m[a.second].insert(a.first);
11        }
12        for(int i=0;i<words1.size();i++){
13            if(words1[i]!=words2[i] && m[words1[i]].count(words2[i])==0)
14                return false;
15        }
16        return true;
17    }
18};

C# Solution

1
2csharp
3public class Solution {
4    public bool AreSentencesSimilar(string[] words1, string[] words2, IList<IList<string>> pairs) {
5        if(words1.Length != words2.Length) return false;
6
7        Dictionary<string, HashSet<string>> map = new Dictionary<string, HashSet<string>>();
8        foreach(var pair in pairs)
9        {
10            if(!map.ContainsKey(pair[0]))
11                map[pair[0]] = new HashSet<string>();
12            
13            if(!map.ContainsKey(pair[1]))
14                map[pair[1]] = new HashSet<string>();
15            
16            map[pair[0]].Add(pair[1]);
17            map[pair[1]].Add(pair[0]);
18        }
19        
20        for(int i=0;i<words1.Length;i++)
21            if(!words1[i].Equals(words2[i]) && (!map.ContainsKey(words1[i]) || !map[words1[i]].Contains(words2[i])))
22                return false;
23
24        return true;
25    }
26}

These are the solutions in Python, Java, Javascript, C++, and C#. All the solutions follow a similar approach:

1. Check if the length of both sentences are equal. If they are not equal, return false.

2. Construct a map (or dictionary in Python, and C#) from the list of pairs, with each word in the pair being a key to a set of its similar words.

3. Iterate over the words in both sentences. If a word in sentence1 is neither identical to its corresponding word in sentence2, nor listed as its similar word, return false.

4. If all the corresponding words are either identical or similar, return true.

If the problem does not specify the data structures to use, the choice of data structures (list, set, map or dictionary) is based on the requirements for performance, such as time complexity. A set and map (dictionary in python) are often used to check existence of an item efficiently (in constant time).