[Google Question] Determine if given two sentences are similar or not

Problem: Given two sentences each represented as a string array and an array of string pairs where every pair [w1, w2] indicates that the two words w1 and w2 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)
• Words at every index in  both sentences are similar.

Note that:

• Every word is similar to itself.
• Similarity is not transitive. For example, if the words w1 and w2 are similar and the words w2 and w3 are similar, w1 and w3 are not necessarily similar.

Example:

Input: sentence1 = ["good","bad","actions"], sentence2 = ["fine","worst","actions"], similarPairs = [["good","fine"],["bad","worst"]]
Output: true
Explanation: The two sentences have the same length and each word wi of sentence1 is also similar to the corresponding word in sentence2.

Approach: We just need to create a hash where key is word and value is hash set of similar words from given similar pairs. Once this hash is generated we can use it to efficiently check the similarity relation of each word. That's all!

Implementation in C#:

    public bool AreSentencesSimilar(string[] sentence1, string[] sentence2, IList<IList<string>> similarPairs) {

        if (sentence1.Length != sentence2.Length)

        {

            return false;

        }

        Dictionary<string, HashSet<string>> similarWordsMap = new Dictionary<string, HashSet<string>>();

        foreach(List<string> similarWords in similarPairs)

        {

            if (!similarWordsMap.ContainsKey(similarWords[0]))

            {

                similarWordsMap.Add(similarWords[0], new HashSet<string>());

            }

            similarWordsMap[similarWords[0]].Add(similarWords[1]);

        }

        for (int i = 0; i < sentence1.Length; ++i)

        {

            if (!this.IsSimilarWords(sentence1[i], sentence2[i], similarWordsMap))

            {

                return false;

            }

        }

        return true;

    }

    

    private bool IsSimilarWords(string word1, string word2, Dictionary<string, HashSet<string>> similarWordsMap)

    {

        if (word1 == word2)

        {

            return true;

        }

        if (similarWordsMap.ContainsKey(word1))

        {

            if (similarWordsMap[word1].Contains(word2))

            {

                return true;

            }

        }

        if (similarWordsMap.ContainsKey(word2))

        {

            if (similarWordsMap[word2].Contains(word1))

            {

                return true;

            }

        }        

        return false;

    }

Complexity: O(n)