Created
November 28, 2019 23:54
-
-
Save rohandalvi/a0923f28bf2ec48c1a2d248b9cd09980 to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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