Q40 Leetcode 734. Sentence Similarity
Mon Jun 12 2023 09:25:08 GMT+0000 (Coordinated Universal Time)
Saved by
@Ayush_dabas07
public boolean areSentencesSimiliar(String[] sentence1 , String[] sentence2) {
/* Q40 graph playlist , basically applying DSU for strings we will make parent and
rank in HM<String , String> and rank HM<String ,Integer>
*/
parent = new HashMap<>();
size = new HashMap<>();
int n = sentence1.length;
if(sentence1.length != sentence2.length)
return false;
//union all the pairs
for(String[] p : pairs){
union(p[0] , p[1]);
}
//now process sentence1 & 2 simultaneously and check similarity
for(int i = 0 ; i < n ; i++){
String w1 = setence1[i];
String w2 = sentence2[i];
if(w1.equals(w2) == false && find(w1).equals(find(w2) == false))
return false
}
return true;
}
HashMap<String, String> parent;
HashMap<String , Integer> size;
public String find(String str){
//if coming first time
if(parent.containsKey(str) == false){
parent.put(str , str);
size.put(str , 1);
}
//now normal find
if(str.equals(parent.get(str)) == true)
return x;
String temp = find(parent.get(str))
parent.put(str , temp);
return temp;
}
public void union(String x , String y){
String lx = find(x);
String ly = find(y);
if(lx.equals(ly) == false){
if(size.get(lx) > size.get(ly)){
parent.put(ly , lx);
}
else{
parent.put(lx , ly);
if(size.get(lx) == size.get(ly))
size.put(ly , size.get(ly) + 1);
}
}
}
content_copyCOPY
https://leetcode.ca/all/734.html
Comments