Skip to content

Instantly share code, notes, and snippets.

@rohandalvi
Created November 27, 2019 04:18
Show Gist options
  • Save rohandalvi/01f8abc0a84ee0b627620fca91022175 to your computer and use it in GitHub Desktop.
Save rohandalvi/01f8abc0a84ee0b627620fca91022175 to your computer and use it in GitHub Desktop.
Sentence similarity
class Solution {
private static Map<String, Set<String>> map = new LinkedHashMap<>();
private static Map<String, String> temp = new HashMap<>();
public boolean areSentencesSimilarTwo(String[] words1, String[] words2, List<List<String>> pairs) {
if(words1.length != words2.length) return false;
populate(pairs);
transformMap();
String[] s1 = transform(words1);
String[] s2 = transform(words2);
for(int i = 0;i<s1.length;i++) {
if(!s1[i].equals(s2[i])) return false;
}
map.clear();
temp.clear();
return true;
}
private String[] transform(String[] words) {
String[] result = new String[words.length];
for(int i = 0;i<words.length;i++) {
if(temp.containsKey(words[i])) {
result[i] = temp.get(words[i]);
} else {
result[i] = words[i];
}
}
return result;
}
private void transformMap() {
for(String key: map.keySet()) {
Set<String> values = map.get(key);
for(String value: values) {
temp.put(value, key);
}
}
}
private void populate(List<List<String>> pairs) {
for(List<String> list: pairs ) {
String key = list.get(0);
String value = list.get(1);
String v;
if(map.containsKey(key)) {
map.get(key).add(value);
} else {
if(map.containsKey(value)) {
map.get(value).add(key);
} else if ((v=getMysteriousKey(key, value))!=null){
map.get(v).add(key);
map.get(v).add(value);
}else {
map.put(key, new HashSet<>());
map.get(key).add(value);
}
}
}
}
private String getMysteriousKey(String k, String v) {
for(String key: map.keySet()) {
if(map.get(key).contains(k) || map.get(key).contains(v)) return key;
}
return null;
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment