https://leetcode.com/problems/sentence-similarity-ii

Solution.java

class Solution {
    public boolean areSentencesSimilarTwo(String[] words1, String[] words2, List<List<String>> pairs) {
        if(words1.length != words2.length) return false;
        Graph<String> graph = new Graph();
        for(List<String> list: pairs) {
            String key = list.get(0);
            String value = list.get(1);
            if(!key.equals(value)) {
                graph.addNode(key);
                graph.addNode(value);
            
                graph.addEdge(key, value);    
            }
        }
        
        for(int i=0;i<words1.length;i++) {
            String key = words1[i];
            String value = words2[i];
            
            if(!key.equals(value) && !graph.dfs(key).contains(value) && !graph.dfs(value).contains(key)) return false;
        }
        return true;
    }
    
    class Graph<T> {
        private Map<T, List<T>> map;

    Graph() {
        map = new HashMap<>();
    }


    public void addNode(T obj) {
        if(map.containsKey(obj)) return;
        map.put(obj, new ArrayList<>());
    }


    public void addEdge(T obj1, T obj2) {
        if(!map.containsKey(obj1) && !map.containsKey(obj2)) {
            throw new NullPointerException("Neither object exists in the graph");
        }
        map.putIfAbsent(obj1, new ArrayList<>());
        map.putIfAbsent(obj2, new ArrayList<>());

        if(!map.get(obj1).contains(obj2)) {
            map.get(obj1).add(obj2);
        }

        if(!map.get(obj2).contains(obj1)) {
            map.get(obj2).add(obj1);
        }

    }


    public List<T> dfs(T obj) {
        if(!map.containsKey(obj)) return new ArrayList<>();
        List<T> list = new ArrayList<>();
        Set<T> visited = new HashSet<>();
        helper(obj, list, visited);
        return list;
    }

    private void helper(T obj, List<T> list, Set<T> visited) {
        if(visited.contains(obj)) return;
        visited.add(obj);
        list.add(obj);
        for(T t: map.get(obj)) {
            helper(t, list, visited);
        }
    }
    }
}