737. Sentence Similarity II

DFS 的套路也就这么多吧， 这也是一个经典的DFS套路。
也可以用Union Find写。

class Solution {
    public boolean areSentencesSimilarTwo(String[] words1, String[] words2, String[][] pairs) {
        if (words1.length != words2.length) return false;
        Map<String, Set<String>> graph = new HashMap<>();
        Map<String, Integer> stringIds = new HashMap<>();
        buildGraph(pairs, graph);
        buildIdMap(graph, stringIds);
        for (int i = 0; i < words1.length; i++) {
            if (words1[i].equals(words2[i])) continue;
            if (stringIds.get(words1[i]) == null ||
               stringIds.get(words2[i]) == null ||
               stringIds.get(words1[i]) != stringIds.get(words2[i])) return false;
        }
        return true;
    }
    private void buildGraph(String[][] pairs, Map<String, Set<String>> graph) {
        for (String[] pair : pairs) {
            String w1 = pair[0], w2 = pair[1];
            graph.putIfAbsent(w1, new HashSet<>());
            graph.putIfAbsent(w2, new HashSet<>());
            graph.get(w1).add(w2);
            graph.get(w2).add(w1);
        }
    }
    private void buildIdMap(Map<String, Set<String>> graph, Map<String, Integer> stringIds) {
        int id = 0;
        for (String w : graph.keySet()) {
            if (stringIds.get(w) == null) {
                dfsHelper(graph, w, stringIds, id);
                id++;
            }
        }
    }
    private void dfsHelper(Map<String, Set<String>> graph, String w, Map<String, Integer> stringIds,
                          int id) {
        if (stringIds.get(w) != null) return; // let base case do the dirty works
        stringIds.put(w, id);
        if (graph.get(w) == null) return;
        for (String wNext : graph.get(w)) {
            dfsHelper(graph, wNext, stringIds, id);
        }
    }
}

下面是Union Find的解法，一遍bug free, typo free !

class Solution {
    public boolean areSentencesSimilarTwo(String[] words1, String[] words2, String[][] pairs) {
        Map<String, Integer> idMap = new HashMap<>();
        int id = 0;
        for (String[] p : pairs) {
            if (!idMap.containsKey(p[0])) idMap.put(p[0], id++);
            if (!idMap.containsKey(p[1])) idMap.put(p[1], id++);
        }
        UnionFind uf = new UnionFind(id);
        for (String[] p : pairs) {
            uf.union(idMap.get(p[0]), idMap.get(p[1]));
        }
        if (words1.length != words2.length) return false;
        for (int i = 0; i < words1.length; i++) {
            String w1 = words1[i], w2 = words2[i];
            if (w1.equals(w2)) continue;
            if (!idMap.containsKey(w1) ||
               !idMap.containsKey(w2)) return false;
            if (uf.root(idMap.get(w1)) != uf.root(idMap.get(w2))) return false;
        }
        return true;
    }
}
class UnionFind {
    int[] ids;
    int[] weights;
    public UnionFind(int n) {
        ids = new int[n];
        weights = new int[n];
        for (int i = 0; i < n; i++) {
            ids[i] = i;
            weights[i] = 1;
        }
    }
    public int root(int id) {
        if (ids[id] != id){
            ids[id] = root(ids[id]);
        }
        return ids[id];
    }
    public boolean union(int id1, int id2) {
        int root1 = root(id1), root2 = root(id2);
        if (root1 == root2) return false;
        if (weights[root1] >= weights[root2]) {
            ids[root2] = root1;
            weights[root1] += weights[root2];
        } else {
            ids[root1] = root2;
            weights[root2] += weights[root1];
        }
        return true;
    }
}