package com.fishercoder.solutions;

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

/**
 * 737. Sentence Similarity II
 *
 * Given two sentences words1, words2 (each represented as an array of strings), and a list of similar word pairs pairs, determine if two sentences are similar.
 * For example, words1 = ["great", "acting", "skills"] and words2 = ["fine", "drama", "talent"] are similar,
 * if the similar word pairs are pairs = [["great", "good"], ["fine", "good"], ["acting","drama"], ["skills","talent"]].
 * Note that the similarity relation is transitive.
 *
 * For example, if "great" and "good" are similar, and "fine" and "good" are similar, then "great" and "fine" are similar.
 * Similarity is also symmetric. For example, "great" and "fine" being similar is the same as "fine" and "great" being similar.
 * Also, a word is always similar with itself. For example, the sentences words1 = ["great"], words2 = ["great"], pairs = [] are similar, even though there are no specified similar word pairs.
 * Finally, sentences can only be similar if they have the same number of words. So a sentence like words1 = ["great"] can never be similar to words2 = ["doubleplus","good"].

 Note:

 The length of words1 and words2 will not exceed 1000.
 The length of pairs will not exceed 2000.
 The length of each pairs[i] will be 2.
 The length of each words[i] and pairs[i][j] will be in the range [1, 20].

 */
public class _737 {
    public static class Solution1 {
        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]);
                }

                setParent(map, pair[0], pair[1]);
            }

            for (int i = 0; i < words1.length; i++) {
                String parent1 = getParent(map, words1[i]);
                String parent2 = getParent(map, words2[i]);
                if (!parent1.equals(parent2)) {
                    return false;
                }
            }
            return true;
        }

        private void setParent(Map<String, String> map, String word1, String word2) {
            String parent1 = getParent(map, word1);
            String parent2 = getParent(map, word2);
            map.put(parent1, parent2);
        }

        private String getParent(Map<String, String> map, String word) {
            if (!map.containsKey(word)) {
                return word;
            }
            while (!word.equals(map.get(word))) {
                word = map.get(word);
            }
            return word;
        }
    }
}

@@ -82,1338 +82,8 @@
 p;%0A%0A
-/**%0A * 737. Sentence Similarity II%0A *%0A * Given two sentences words1, words2 (each represented as an array of strings), and a list of similar word pairs pairs, determine if two sentences are similar.%0A * For example, words1 = %5B%22great%22, %22acting%22, %22skills%22%5D and words2 = %5B%22fine%22, %22drama%22, %22talent%22%5D are similar,%0A * if the similar word pairs are pairs = %5B%5B%22great%22, %22good%22%5D, %5B%22fine%22, %22good%22%5D, %5B%22acting%22,%22drama%22%5D, %5B%22skills%22,%22talent%22%5D%5D.%0A * Note that the similarity relation is transitive.%0A *%0A * For example, if %22great%22 and %22good%22 are similar, and %22fine%22 and %22good%22 are similar, then %22great%22 and %22fine%22 are similar.%0A * Similarity is also symmetric. For example, %22great%22 and %22fine%22 being similar is the same as %22fine%22 and %22great%22 being similar.%0A * Also, a word is always similar with itself. For example, the sentences words1 = %5B%22great%22%5D, words2 = %5B%22great%22%5D, pairs = %5B%5D are similar, even though there are no specified similar word pairs.%0A * Finally, sentences can only be similar if they have the same number of words. So a sentence like words1 = %5B%22great%22%5D can never be similar to words2 = %5B%22doubleplus%22,%22good%22%5D.%0A%0A Note:%0A%0A The length of words1 and words2 will not exceed 1000.%0A The length of pairs will not exceed 2000.%0A The length of each pairs%5Bi%5D will be 2.%0A The length of each words%5Bi%5D and pairs%5Bi%5D%5Bj%5D will be in the range %5B1, 20%5D.%0A%0A */%0A
 publ

refactor 737