Java solution, HashMap & HashSet


  • 1

    Time complexity: O(nk), space complexity O(nk). n is number of words, k is the average length of words.

    class Solution {
        public boolean areSentencesSimilar(String[] words1, String[] words2, String[][] pairs) {
            if (words1.length != words2.length) return false;
            Map<String, Set<String>> map = new HashMap<>();
            
            for (String[] p : pairs) {
                Set<String> set0 = map.getOrDefault(p[0], new HashSet<>());
                set0.add(p[1]);
                map.put(p[0], set0);
                
                Set<String> set1 = map.getOrDefault(p[1], new HashSet<>());
                set1.add(p[0]);
                map.put(p[1], set1);
            }
            
            for (int i = 0; i < words1.length; i++) {
                if (words1[i].equals(words2[i])) continue;
                if (map.containsKey(words1[i]) && map.get(words1[i]).contains(words2[i])) continue;
                return false;
            }
            
            return true;
        }
    }
    

  • 0
    C

    why time complexity is nk? because equals() method cost average O(k) time?


Log in to reply
 

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