Sentence Similarity

Problem

We can represent a sentence as an array of words, for example, the sentence "I am happy with leetcode" can be represented as arr = ["I","am",happy","with","leetcode"].

Given two sentences sentence1 and sentence2 each represented as a string array and given an array of string pairs similarPairs where similarPairs[i] = [xi, yi] indicates that the two words xi and yi are similar.

Return true if sentence1 and sentence2 are similar, or false if they are not similar.

Two sentences are similar if:

• They have the same length (i.e., the same number of words)
• sentence1[i] and sentence2[i] are similar.

Notice that a word is always similar to itself, also notice that the similarity relation is not transitive. For example, if the words a and b are similar, and the words b and c are similar, a and c are not necessarily similar.

Constraints

• 1 <= sentence1.length, sentence2.length <= 1000
• 1 <= sentence1[i].length, sentence2[i].length <= 20
• sentence1[i] and sentence2[i] consist of English letters.
• 0 <= similarPairs.length <= 1000
• similarPairs[i].length == 2
• 1 <= xi.length, yi.length <= 20
• xi and yi consist of lower-case and upper-case English letters.
• All the pairs (xi, yi) are distinct.

Solution

The problem Sentence Similarity can be solved using a hash map. Since the similarities are not transitive, we cannot use disjoint-set for this problem. Instead, by storing each pairs of similar words into a hash map, we can identify if all words in given sentences are similar or not.

Implementation

static const int fast_io = []()
{
    std::ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    return 0;
}();

class Solution
{
  public:
    bool areSentencesSimilar(vector<string> &sentence1, vector<string> &sentence2, vector<vector<string>> &similarPairs)
    {
        if (sentence1.size() != sentence2.size())
            return false;

        unordered_set<string> hashmap;
        for (auto pairs : similarPairs)
        {
            hashmap.insert(pairs[0] + " " + pairs[1]);
            hashmap.insert(pairs[1] + " " + pairs[0]);
        }

        for (int i = 0; i < sentence1.size(); i++)
        {
            if (sentence1[i] == sentence2[i])
                continue;
            if (hashmap.find(sentence1[i] + " " + sentence2[i]) == hashmap.end())
                return false;
        }

        return true;
    }
};