Simple Python Solution - 32ms!


  • 6

    We use a dictionary to map words with their similar words and simply look up the dictionary when we compare pairs of words in words1 and words2 by checking if the second word is in the first word's similar word set.

    For this pairs of words, the following dict is generated:

    [["a", "b"], ["a", "c"], ["b", "d"]]

    {
      "a": set(["b", "c"]),
      "b": set(["a", "d"]),
      "c": set(["a"]),
      "d": set(["b"]),
    }
    

    - Yangshun

    class Solution(object):
        def areSentencesSimilar(self, words1, words2, pairs):
            from collections import defaultdict
            if len(words1) != len(words2):
                return False
            words = defaultdict(set)
            for word1, word2 in pairs:
                words[word1].add(word2)
                words[word2].add(word1)
            for word1, word2 in zip(words1, words2):
                if word1 != word2 and word2 not in words[word1]:
                    return False
            return True
    

  • 0
    F

    Time complexity is o(n+p) and space complexity is o(p), where n = num of words to compare and p = num of word pairs.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.