Simple Java Union Find


  • 4
    G
    public boolean areSentencesSimilarTwo(String[] words1, String[] words2, String[][] pairs) {
            
            if(words1.length!=words2.length)
                return false;
            
            Map<String,String> map = new HashMap<String,String>();
            
            for(String[] pair : pairs){
                
                String word1 = pair[0];
                String word2 = pair[1];
                
                if(!map.containsKey(word1))
                    map.put(word1,word1);
                if(!map.containsKey(word2))
                    map.put(word2,word2);
                
                setParent(map,word1,word2);
                
            }
            
            for(int i=0;i<words1.length;i++){
                
                String word1 = words1[i];
                String word2 = words2[i];
                
                String parent1 = getParent(word1,map);
                String parent2 = getParent(word2,map);
                
                if(!parent1.equals(parent2))
                    return false;
         
            }
            return true;
            
            
        }
        
        public String getParent(String word,Map<String,String> map){
            
            if(!map.containsKey(word))
                return word;
            
            while(word!=map.get(word))
                word = map.get(word);
            return word;
      
        }
        
        public void setParent(Map<String,String> map,String word1,String word2){
            
            String p1 = getParent(word1,map);
            String p2 = getParent(word2,map);
            
            map.put(p1,p2);
       
        }
    

  • 1
    E

    Thanks, this is my Python union-find solution.


  • 0
    T

    here is another java union found solution:

    class Solution {
        public boolean areSentencesSimilarTwo(String[] words1, String[] words2, String[][] pairs) {
            if(words1.length!=words2.length){
                return false;
            }
            
            Map<String,String> map = new HashMap<>();
            for(String[] ele:pairs){
                map.put(ele[0],ele[0]);
                map.put(ele[1],ele[1]);
            }
            
            for(String[] ele:pairs){
                String par1 = findParent(ele[0],map);
                String par2 = findParent(ele[1],map);
                if(!par1.equals(par2)){
                    map.put(par1,par2);
                }
            }
            for(int i=0;i<words1.length;i++){
                if(words1[i].equals(words2[i])){
                    continue;
                }
                if(!map.containsKey(words1[i]) || !map.containsKey(words2[i])){
                    return false;
                }
                String par1 = findParent(words1[i],map);
                String par2 = findParent(words2[i],map);
                if(!par1.equals(par2)){
                    return false;
                }
            }
            
            return true;
            
        }
        
        public String findParent(String str,Map<String,String> map){
             while(!str.equals(map.get(str))){
                  map.put(str,map.get(str));
                  str = map.get(str);              
             }
            
             return str;
        }
    }
    

Log in to reply
 

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