Sentence Similarity
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.
source: https://leetcode.com/problems/sentence-similarity/
Example 1:
Input: sentence1 = ["great","acting","skills"], sentence2 = ["fine","drama","talent"], similarPairs = [["great","fine"],["drama","acting"],["skills","talent"]]
Output: true
Explanation: The two sentences have the same length and each word i of sentence1 is also similar to the corresponding word in sentence2.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 |
class Solution { public boolean areSentencesSimilar(String[] sentence1, String[] sentence2, List<List<String>> similarPairs) { Map<String, Set<String>> mapA = new HashMap<>(); Map<String, Set<String>> mapB = new HashMap<>(); for(List<String> l: similarPairs){ Set<String> setA = mapA.getOrDefault(l.get(0), new HashSet<>()); setA.add(l.get(1)); mapA.put(l.get(0), setA); Set<String> setB = mapB.getOrDefault(l.get(1), new HashSet<>()); setB.add(l.get(0)); mapB.put(l.get(1), setB); } if(sentence1.length==sentence2.length){ for(int i=0;i<sentence1.length;i++){ //check similarity for each word if(!isSimilar(sentence1[i], sentence2[i], mapA, mapB)){ return false; } } return true; } return false; } //Similarity Conditions private boolean isSimilar(String a, String b, Map<String, Set<String>> mapA, Map<String, Set<String>> mapB){ return a.equals(b) || (mapA.containsKey(a) && mapA.get(a).contains(b)) || (mapB.containsKey(a) && mapB.get(a).contains(b)); } } |