734. Sentence Similarity/737. Sentence Similarity II

class Solution {
    public boolean areSentencesSimilar(String[] words1, String[] words2, List<List<String>> pairs) {
        if (words1.length != words2.length) {
            return false;
        }
        Map<String, Set<String>> map = new HashMap<>();
        for (List<String> pair : pairs) {
            String word1 = pair.get(0);
            String word2 = pair.get(1);
            if (!map.containsKey(word1)) {
                map.put(word1, new HashSet<>());
            }
            if (!map.containsKey(word2)) {
                map.put(word2, new HashSet<>());
            }
            map.get(word1).add(word2);
            map.get(word2).add(word1);
        }
        for (int i = 0; i < words1.length; i++) {
            if (words1[i].equals(words2[i])) {
                continue;
            }
            if (!map.containsKey(words1[i])) {
                return false;
            }
            if (!map.get(words1[i]).contains(words2[i])) {
                return false;
            }
        }
        return true;
    }
}

class Solution {
    public boolean areSentencesSimilarTwo(String[] words1, String[] words2, List<List<String>> pairs) {
        if (words1.length != words2.length) {
            return false;
        }
        Map<String, Set<String>> graph = new HashMap<>();
        for (List<String> pair : pairs) {
            String word1 = pair.get(0);
            String word2 = pair.get(1);
            if (!graph.containsKey(word1)) {
                graph.put(word1, new HashSet<>());
            }
            if (!graph.containsKey(word2)) {
                graph.put(word2, new HashSet<>());
            }
            graph.get(word1).add(word2);
            graph.get(word2).add(word1);
        }
        for (int i = 0; i < words1.length; i++) {
            if (words1[i].equals(words2[i])) {
                continue;
            }
            if (!graph.containsKey(words1[i])) {
                return false;
            }
            Set<String> visited = new HashSet<>();
            if (!dfs(graph, words1[i], words2[i], visited)) {
                return false;
            }
        }
        return true;        
    }
    
    private boolean dfs(Map<String, Set<String>> graph, String source, String target, Set<String> visited) {
        if (graph.get(source).contains(target)) {
            return true;
        }
        if (!visited.contains(source)) {
            visited.add(source);
            for (String next : graph.get(source)) {
                if (!visited.contains(next) && dfs(graph, next, target, visited)) {
                    return true;
                }
            }
        }
        return false;
    }
}