Sentence Similarity II — Leetcode 737

Original problem link: https://leetcode.com/problems/sentence-similarity-ii/description/

In this problem, we’re given two sentences as String arrays of each word and a list of “similar” word pairs. It asks if the two sentences are similar, e.g. that they’re the same length and that the words at each index are similar. Similarity is transitive — e.g. if a is similar to b and b similar to c then a is similar to c. Also, two identical words are always similar.

We can use both DFS and union find for this problem, since we can picture this as a graph where vertices (words) that are similar are connected to each other in similarity groups. We need to find out whether words are in the same group or not.

Here is the DFS solution:

class Solution {

    Map<String, Set<String>> graph;
    Set<String> visited;

    public boolean areSentencesSimilarTwo(String[] sentence1, String[] sentence2, List<List<String>> similarPairs) {
        if (sentence1.length != sentence2.length) {
            return false;
        }

        graph = new HashMap<>();
        visited = new HashSet<>();
        for (List<String> pair : similarPairs) {
            String word1 = pair.get(0);
            String word2 = pair.get(1);
            if (graph.containsKey(word1)) {
                graph.get(word1).add(word2);
            } else {
                Set<String> neighbors = new HashSet<>();
                neighbors.add(word2);
                graph.put(word1, neighbors);
            }
            if (graph.containsKey(word2)) {
                graph.get(word2).add(word1);
            } else {
                Set<String> neighbors = new HashSet<>();
                neighbors.add(word1);
                graph.put(word2, neighbors);
            }
        }

        for (int i = 0; i < sentence1.length; i++) {
            if (!isSimilar(sentence1[i], sentence2[i])) {
                return false;
            }
            visited.clear();
        }
        return true;
    }

    private boolean isSimilar(String word, String target) {
        if (word.equals(target)) {
            return true;
        }
        if (!graph.containsKey(word) || !graph.containsKey(target)) {
            return false;
        }

        visited.add(word);
        Set<String> neighbors = graph.get(word);
        for (String n : neighbors) {
            if (!visited.contains(n)) {
                visited.add(n);
                if (isSimilar(n, target)) {
                    return true;
                }
            }
        }
        return false;
    }
}

The DFS solution (above) beats 34% of submissions, but union find (below) is faster.

class Solution {

    Map<String, Integer> groups;
    Map<Integer, Integer> groupIds;
    int nextId;

    public boolean areSentencesSimilarTwo(String[] sentence1, String[] sentence2, List<List<String>> similarPairs) {
        if (sentence1.length != sentence2.length) {
            return false;
        }
        if (similarPairs.isEmpty()) {
            return false;
        }
        
        nextId = 0;
        groups = new HashMap<>();
        groupIds = new HashMap<>();
        for (int i = 0; i < similarPairs.size(); i++) {
            String word1 = similarPairs.get(i).get(0);
            String word2 = similarPairs.get(i).get(1);
            if (!groups.containsKey(word1)) {
                groups.put(word1, nextId);
                groupIds.put(nextId, nextId);
                nextId++;
            }
            if (!groups.containsKey(word2)) {
                groups.put(word2, nextId);
                groupIds.put(nextId, nextId);
                nextId++;
            }
        }

        for (int i = 0; i < similarPairs.size(); i++) {
            String word1 = similarPairs.get(i).get(0);
            String word2 = similarPairs.get(i).get(1);
            union(word1, word2);
        }

        for (int i = 0; i < sentence1.length; i++) {
            int rep1 = find(sentence1[i]);
            int rep2 = find(sentence2[i]);

            if (rep1 != rep2) {
                return false;
            }
        }
        return true;
    }

    private int find(String word) {
        if (!groups.containsKey(word)) {
            return -1;
        }
        int id = groups.get(word);
        return findFromId(id);
    }

    private int findFromId(int id) {
        if (groupIds.get(id) == id) {
            return id;
        }

        return findFromId(groupIds.get(id));
    }

    private void union(String word1, String word2) {
        int rep1 = find(word1);
        int rep2 = find(word2);

        if (rep1 == rep2) {
            return;
        }

        if (rep1 != -1 && rep2 != -1) {
            if (rep1 < rep2) {
                groupIds.put(rep2, rep1);
            } else {
                groupIds.put(rep1, rep2);
            }
        }
    }
}

The union find solution beats about 80% of submissions in runtime.