Skip to content

Instantly share code, notes, and snippets.

@rohandalvi
Created November 28, 2019 23:54
Show Gist options
  • Save rohandalvi/a0923f28bf2ec48c1a2d248b9cd09980 to your computer and use it in GitHub Desktop.
Save rohandalvi/a0923f28bf2ec48c1a2d248b9cd09980 to your computer and use it in GitHub Desktop.
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);
}
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment