## Sunday, May 20, 2018

### LeetCode 737 - Sentence Similarity II

Given two sentences `words1, words2` (each represented as an array of strings), and a list of similar word pairs `pairs`, determine if two sentences are similar.
For example, `words1 = ["great", "acting", "skills"]` and `words2 = ["fine", "drama", "talent"]` are similar, if the similar word pairs are `pairs = [["great", "good"], ["fine", "good"], ["acting","drama"], ["skills","talent"]]`.
Note that the similarity relation is transitive. For example, if “great” and “good” are similar, and “fine” and “good” are similar, then “great” and “fine” are similar.
Similarity is also symmetric. For example, “great” and “fine” being similar is the same as “fine” and “great” being similar.
Also, a word is always similar with itself. For example, the sentences `words1 = ["great"], words2 = ["great"], pairs = []` are similar, even though there are no specified similar word pairs.
Finally, sentences can only be similar if they have the same number of words. So a sentence like `words1 = ["great"]` can never be similar to `words2 = ["doubleplus","good"]`.
Note:
• The length of `words1` and `words2` will not exceed `1000`.
• The length of `pairs` will not exceed `2000`.
• The length of each `pairs[i]` will be `2`.
• The length of each `words[i]` and `pairs[i][j]` will be in the range `[1, 20]`.
Time complexity: O(|Pairs| + |words1|)
Space complexity: O(|Pairs|)
(1) 用union find的关键就是要给每个pair里的word分配一个unique id，然后用map存string到id的关系
(2) 在遍历words1和words2，如果map里面没有words1或words2当前的词或者通过find我们发现当前word1和word2不在一个集合里，return false
Union Find: 时间复杂度O(k + n), 空间复杂度O(k)
``````class Solution {
public boolean areSentencesSimilarTwo(String[] words1, String[] words2, String[][] pairs) {
if (words1.length != words2.length) {
return false;
}

UnionFind uf = new UnionFind(2 * pairs.length);

Map<String, Integer> map = new HashMap<>();
int id = 0;

for (String[] pair : pairs) {
for (String word : pair) {
if (!map.containsKey(word)) {
map.put(word, id);
++id;
}
}

uf.union(map.get(pair[0]), map.get(pair[1]));
}

for (int i = 0; i < words1.length; i++) {
String word1 = words1[i];
String word2 = words2[i];

if (word1.equals(word2)) {
continue;
}

if (!map.containsKey(word1) || !map.containsKey(word2) || uf.find(map.get(word1)) != uf.find(map.get(word2))) {
return false;
}
}
return true;
}

class UnionFind {
int[] sets;
int[] size;
int count;

public UnionFind(int n) {
sets = new int[n];
size = new int[n];
count = n;

for (int i = 0; i < n; i++) {
sets[i] = i;
size[i] = 1;
}
}

public int find(int node) {
while (node != sets[node]) {
node = sets[node];
}
return node;
}

public void union(int i, int j) {
int node1 = find(i);
int node2 = find(j);

if (node1 == node2) {
return;
}

if (size[node1] < size[node2]) {
sets[node1] = node2;
size[node2] += size[node1];
}
else {
sets[node2] = node1;
size[node1] += size[node2];
}
--count;
}
}
``````

C++ / Union Find
bool Union(const string& word1, const string& word2) {
const string& p1 = Find(word1, true);
const string& p2 = Find(word2, true);
if (p1 == p2) return false;
parents_[p1] = p2;
return true;
}

const string& Find(const string& word, bool create = false) {
if (!parents_.count(word)) {
if (!create) return word;
return parents_[word] = word;
}

string w = word;
while (w != parents_[w]) {
parents_[w] = parents_[parents_[w]];
w = parents_[w];
}

return parents_[w];
}
private:
unordered_map<string, string> parents_;
};

class Solution {
public:
bool areSentencesSimilarTwo(vector<string>& words1, vector<string>& words2, vector<pair<string, string>>& pairs) {
if (words1.size() != words2.size()) return false;

UnionFindSet s;
for (const auto& pair : pairs)
s.Union(pair.first, pair.second);

for (int i = 0; i < words1.size(); ++i)
if (s.Find(words1[i]) != s.Find(words2[i])) return false;

return true;
}
https://www.jianshu.com/p/43fe7cc6797b

``````    public boolean areSentencesSimilarTwo(String[] words1, String[] words2, String[][] pairs) {
if(words1.length!=words2.length) return false;
Map<String, String> map = new HashMap<>();
for(String[] pair : pairs){
String parent0 = find(pair[0], map);
String parent1 = find(pair[1], map);
if(!parent0.equals(parent1)) map.put(parent0, parent1);
}
int n = words1.length;
for(int i=0; i<n; i++){
if (!words1[i].equals(words2[i]) && !find(words1[i], map).equals(find(words2[i], map))) return false;
}
return true;
}

private String find(String word, Map<String, String> map){
if(!map.containsKey(word)) return word;
String str = word;
while(map.containsKey(str)){
str = map.get(str);
}
map.put(word, str);
return str;
}
``````

X.
DFS: 时间复杂度O(nk), 其中n为words的长度， k为pairs的长度，空间复杂度O(k)
``````    public boolean areSentencesSimilarTwo(String[] words1, String[] words2, String[][] pairs) {
if (words1.length != words2.length) {
return false;
}

Map<String, Set<String>> graph = new HashMap<>();

for (String[] pair : pairs) {
graph.putIfAbsent(pair[0], new HashSet<>());
graph.putIfAbsent(pair[1], new HashSet<>());

}

for (int i = 0; i < words1.length; i++) {
if (words1[i].equals(words2[i])) {
continue;
}

if (!graph.containsKey(words1[i]) || !graph.containsKey(words2[i])) {
return false;
}
Set<String> visited = new HashSet<>();

if (!dfs(words1[i], words2[i], graph, visited)) {
return false;
}
}
return true;
}

public boolean dfs(String startWord, String endWord, Map<String, Set<String>> graph, Set<String> visited) {
if (graph.get(startWord).contains(endWord)) {
return true;
}

if (visited.contains(startWord)) {
return false;
}

for (String nextWord : graph.get(startWord)) {
if (dfs(nextWord, endWord, graph, visited)) {
return true;
}
}
return false;
}```
```
Time complexity: O(|Pairs| + |words1|)
Space complexity: O(|Pairs|)
C++ / DFS Optimized
bool areSentencesSimilarTwo(vector<string>& words1, vector<string>& words2, vector<pair<string, string>>& pairs) {
if (words1.size() != words2.size()) return false;

g_.clear();
ids_.clear();

for (const auto& p : pairs) {
g_[p.first].insert(p.second);
g_[p.second].insert(p.first);
}

int id = 0;

for (const auto& p : pairs) {
if(!ids_.count(p.first)) dfs(p.first, ++id);
if(!ids_.count(p.second)) dfs(p.second, ++id);
}

for (int i = 0; i < words1.size(); ++i) {
if (words1[i] == words2[i]) continue;
auto it1 = ids_.find(words1[i]);
auto it2 = ids_.find(words2[i]);
if (it1 == ids_.end() || it2 == ids_.end()) return false;
if (it1->second != it2->second) return false;
}

return true;
}
private:
bool dfs(const string& curr, int id) {
ids_[curr] = id;
for (const auto& next : g_[curr]) {
if (ids_.count(next)) continue;
if (dfs(next, id)) return true;
}
return false;
}

unordered_map<string, int> ids_;
unordered_map<string, unordered_set<string>> g_;