Q40 Leetcode 734. Sentence Similarity

PHOTO EMBED

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