Union Find with Java 8, clean code


  • 0
    T

    Since there was nothing different about union find, other than use of strings in place of integers, so i decided to separate it out in another class. I always favor clean/modular code against short solutions.

    import java.util.HashMap;
    import java.util.Map;
    public class SimilarCheck {
       
       public static void main(String[] args) {
          String[] words1 = {"great", "acting", "skills"};
          String[] words2 = {"fine", "drama", "talent"};
          String[][] pairs = {{"great", "good"},
                              {"fine", "good"},
                              {"acting","drama"},
                              {"skills","talent"}};
                              
          System.out.println(areSimilar(words1, words2, pairs));
       }
       
       public static boolean areSimilar(String[] words1, String[] words2, String[][] pairs) {
          
          int n = words1.length;
          if (n != words2.length) return false;
          
          UFString uf = new UFString();
          
          for (String[] pair: pairs) {
             uf.union(pair[0], pair[1]);
          }
          
          for (int i = 0; i < n; i++) {
             if (!uf.isConnected(words1[i], words2[i])) return false;
          }
          
          return true;
       }
    }
    
    class UFString {
       private Map<String, String> map;
       public UFString() {
          map = new HashMap<String, String>();
       }
       
       public boolean isConnected(String word1, String word2) {
          return find(word1).equals(find(word2));
       }
       
       /**
        * Connect by making root of word2 as root/parent of word1
        */
       public void union(String word1, String word2) {
          map.put(find(word1), find(word2));
       }
    
       
       // find with path compression
       public String find(String word) {
          // in case a word's parent is not found, word is parent of itself
          while(!word.equals(map.getOrDefault(word, word))) {
             String parent = map.get(word);
             map.put(word, map.getOrDefault(parent, parent));
             word = map.get(word);
          }
          
          return word;
       }
    }
    

Log in to reply
 

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