1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
| class Solution {
public boolean areSentencesSimilarTwo(String[] sentence1, String[] sentence2, List<List<String>> similarPairs) {
if (sentence1.length != sentence2.length) {
return false;
}
Map<String, Set<String>> wordsSimilarSet = new HashMap<>();
for (List<String> pair : similarPairs) {
wordsSimilarSet.putIfAbsent(pair.get(0), new HashSet<>());
wordsSimilarSet.get(pair.get(0)).add(pair.get(1));
wordsSimilarSet.putIfAbsent(pair.get(1), new HashSet<>());
wordsSimilarSet.get(pair.get(1)).add(pair.get(0));
}
for (int i = 0; i < sentence1.length; i++) {
if (sentence1[i].equals(sentence2[i])) {
continue;
}
if (!wordsSimilarSet.containsKey(sentence1[i]) || !wordsSimilarSet.containsKey(sentence2[i])) {
return false;
}
if (!dfs(wordsSimilarSet, sentence1[i], sentence2[i], new HashSet<>())) {
return false;
}
}
return true;
}
private boolean dfs(Map<String, Set<String>> wordsSimilarSet, String word1, String word2, Set<String> visited) {
if (wordsSimilarSet.get(word1).contains(word2)) {
return true;
}
for (String child : wordsSimilarSet.get(word1)) {
if (visited.add(child) && dfs(wordsSimilarSet, child, word2, visited)) {
return true;
}
}
return false;
}
}
|
每个word就是一个node, dfs即可.
时间复杂度: O(V(每个node都要判断是否包含word2) + E(因为for循环要把所有的child都add一遍)) V是pairs中unique words的个数, E是pairs这个list的size, 也就是edge的个数.
空间复杂度: O(V) 可能是链表.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
| class Solution {
private static class UnionFind {
private int[] parent;
private int[] rank;
private UnionFind(int size) {
parent = new int[size];
rank = new int[size];
for (int i = 0; i < parent.length; i++) {
parent[i] = i;
rank[i] = 1;
}
}
private int find(int x) {
if (x == parent[x]) {
return x;
}
return parent[x] = find(parent[x]);
}
private void union(int x, int y) {
int xRoot = find(x);
int yRoot = find(y);
if (xRoot != yRoot) {
if (rank[xRoot] > rank[yRoot]) {
parent[yRoot] = xRoot;
} else if (rank[xRoot] < rank[yRoot]) {
parent[xRoot] = yRoot;
} else {
parent[yRoot] = xRoot;
rank[xRoot] += 1;
}
}
}
private boolean isConnected(int x, int y) {
return find(x) == find(y);
}
}
public boolean areSentencesSimilarTwo(String[] sentence1, String[] sentence2, List<List<String>> similarPairs) {
if (sentence1.length != sentence2.length) {
return false;
}
Map<String, Integer> stringIdxMap = new HashMap<>();
int idx = 0;
UnionFind uf = new UnionFind(similarPairs.size() * 2);
for (List<String> pair : similarPairs) {
if (!stringIdxMap.containsKey(pair.get(0))) {
stringIdxMap.put(pair.get(0), idx++);
}
if (!stringIdxMap.containsKey(pair.get(1))) {
stringIdxMap.put(pair.get(1), idx++);
}
uf.union(stringIdxMap.get(pair.get(0)), stringIdxMap.get(pair.get(1)));
}
for (int i = 0; i < sentence1.length; i++) {
if (sentence1[i].equals(sentence2[i])) {
continue;
}
if (!stringIdxMap.containsKey(sentence1[i]) || !stringIdxMap.containsKey(sentence2[i])
|| !uf.isConnected(stringIdxMap.get(sentence1[i]), stringIdxMap.get(sentence2[i]))) {
return false;
}
}
return true;
}
}
|
Union Find(path compression + union by rank)
时间复杂度: O(N + P) N是sentence1的length因为我们要遍历. 每次遍历平均是O(1). P是pair的长度, 因为我们要往map中添加string以及UF中union string. 都是平均O(1).
空间负复杂度: O(P) UF需要parent和rank数组, 都是P的二倍, 是O(2P), map也是O(P). 加在一起是O(3P)也就是O(P).
