package leetcode;

import java.util.HashMap;
import java.util.Map;

/**
 * https://leetcode.com/problems/sentence-similarity-ii/
 */
public class Problem737 {
    public boolean areSentencesSimilarTwo(String[] words1, String[] words2, String[][] pairs) {
        if (words1.length != words2.length) {
            return false;
        }
        Map<String, String> map = new HashMap<>();
        for (String[] pair : pairs) {
            if (!map.containsKey(pair[0])) {
                map.put(pair[0], pair[0]);
            }
            if (!map.containsKey(pair[1])) {
                map.put(pair[1], pair[1]);
            }
            if (!find(map, pair[0]).equals(find(map, pair[1]))) {
                map.put(pair[0], pair[1]);
            }
        }
        for (int i = 0; i < words1.length; i++) {
            String word1 = words1[i];
            String word2 = words2[i];
            if (word1.equals(word2)) {
                continue;
            }
            if (!map.containsKey(word1)) {
                return false;
            }
            if (!map.containsKey(word2)) {
                return false;
            }
            if (!find(map, word1).equals(find(map, word2))) {
                return false;
            }
        }
        return true;
    }

    private static String find(Map<String, String> map, String word) {
        String key = word;
        String value = map.get(key);
        while (!key.equals(value)) {
            key = value;
            value = map.get(key);
        }
        return value;
    }

    public static void main(String[] args) {
        Problem737 prob = new Problem737();
        System.out.println(prob.areSentencesSimilarTwo(
            new String[]{"great", "acting", "skills"},
            new String[]{"fine", "drama", "talent"},
            new String[][]{{"great", "good"}, {"fine", "good"}, {"acting","drama"}, {"skills","talent"}}
        )); // true
        System.out.println(prob.areSentencesSimilarTwo(
            new String[]{"great"},
            new String[]{"great"},
            new String[][]{}
        )); // true
        System.out.println(prob.areSentencesSimilarTwo(
            new String[]{"great"},
            new String[]{"fine"},
            new String[][]{{"great", "good"}, {"fine", "good"}}
        )); // true
        System.out.println(prob.areSentencesSimilarTwo(
            new String[]{"great"},
            new String[]{"great", "blah"},
            new String[][]{}
        )); // false
    }
}

@@ -627,37 +627,46 @@
   %7D%0A            
-if (!
+String val1 = 
 find(map, pair%5B0
@@ -671,34 +671,89 @@
 %5B0%5D)
-.equals(find(map, pair%5B1%5D)
+;%0A            String val2 = find(map, pair%5B1%5D);%0A            if (!val1.equals(val2
 )) %7B
@@ -781,24 +781,18 @@
 put(
-pair%5B0%5D, pair%5B1%5D
+val1, val2
 );%0A 
@@ -1035,122 +1035,128 @@
     
-if (!map.containsKey(word1)) %7B%0A                return false;%0A            %7D%0A            if (!map.containsKey(word2)
+String val1 = find(map, word1);%0A            String val2 = find(map, word2);%0A            if (val1 == null %7C%7C val2 == null
 ) %7B%0A
@@ -1220,48 +1220,24 @@
 f (!
-find(map, word1).equals(find(map, word2)
+val1.equals(val2
 )) %7B
@@ -1446,32 +1446,96 @@
 = map.get(key);%0A
+        if (value == null) %7B%0A            return null;%0A        %7D%0A
         while (!
@@ -1655,960 +1655,7 @@
    %7D
-%0A%0A    public static void main(String%5B%5D args) %7B%0A        Problem737 prob = new Problem737();%0A        System.out.println(prob.areSentencesSimilarTwo(%0A            new String%5B%5D%7B%22great%22, %22acting%22, %22skills%22%7D,%0A            new String%5B%5D%7B%22fine%22, %22drama%22, %22talent%22%7D,%0A            new String%5B%5D%5B%5D%7B%7B%22great%22, %22good%22%7D, %7B%22fine%22, %22good%22%7D, %7B%22acting%22,%22drama%22%7D, %7B%22skills%22,%22talent%22%7D%7D%0A        )); // true%0A        System.out.println(prob.areSentencesSimilarTwo(%0A            new String%5B%5D%7B%22great%22%7D,%0A            new String%5B%5D%7B%22great%22%7D,%0A            new String%5B%5D%5B%5D%7B%7D%0A        )); // true%0A        System.out.println(prob.areSentencesSimilarTwo(%0A            new String%5B%5D%7B%22great%22%7D,%0A            new String%5B%5D%7B%22fine%22%7D,%0A            new String%5B%5D%5B%5D%7B%7B%22great%22, %22good%22%7D, %7B%22fine%22, %22good%22%7D%7D%0A        )); // true%0A        System.out.println(prob.areSentencesSimilarTwo(%0A            new String%5B%5D%7B%22great%22%7D,%0A            new String%5B%5D%7B%22great%22, %22blah%22%7D,%0A            new String%5B%5D%5B%5D%7B%7D%0A        )); // false%0A    %7D
 %0A%7D%0A

Solve problem 737