IVN
0%

Sentence Similarity

Posted on Edited on In
Symbols count in article: 1.8k Reading time ≈ 2 mins.

Sentence Similarity

734. Sentence Similarity

not transitive:

  • HashSet
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public boolean areSentencesSimilar(String[] sentence1, String[] sentence2, List<List<String>> similarPairs) {
    int n=sentence1.length;
    if(n!= sentence2.length){
        return false;
    }
    HashSet<String> set=new HashSet<>();
    for (List<String> similarPair : similarPairs) {
        String a=similarPair.get(0);
        String b=similarPair.get(1);
        set.add(a+b);
    }
    for (int i = 0; i < n; i++) {
        String s1=sentence1[i];
        String s2=sentence2[i];
        if(s1.equals(s2)){
            continue;
        }
        if(!set.contains(s1+s2) && !set.contains(s2+s1)){
            return false;
        }
    }
    return true;
}

737. Sentence Similarity II

transitive:

  • BFS search
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
public boolean areSentencesSimilarTwo(String[] sentence1, String[] sentence2, List<List<String>> similarPairs) {
    int n=sentence1.length;
    if(n!= sentence2.length){
        return false;
    }
    Map<String, List<String>> map=new HashMap<>();
    for (List<String> similarPair : similarPairs) {
        String a=similarPair.get(0);
        String b=similarPair.get(1);
        map.putIfAbsent(a,new LinkedList<>());
        map.get(a).add(b);
        map.putIfAbsent(b,new LinkedList<>());
        map.get(b).add(a);
    }
    Deque<String> q=new LinkedList<>();
    Set<String> visited=new HashSet<>();
    for (int i = 0; i < n; i++) {
        String s1=sentence1[i];
        String s2=sentence2[i];
        if(s1.equals(s2)){
            continue;
        }
        q.clear();
        visited.clear();
        q.offer(s1);
        boolean found=false;
        while(!q.isEmpty()){
            String cur=q.poll();
            if(cur.equals(s2)){
                found=true;
                break;
            }
            if(map.containsKey(cur)){
                for (String next : map.get(cur)) {
                    if(!visited.contains(next)){
                        q.offer(next);
                        visited.add(next);
                    }
                }
            }
        }
        if(!found){
            return false;
        }
    }
    return true;
}