[LeetCode/LintCode] Sentence Similarity

dreamtecher 发布于2019-08-16 12:44 / 2871人阅读

Problem

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, "great acting skills" and "fine drama talent" are similar, if the similar word pairs are pairs = [["great", "fine"], ["acting","drama"], ["skills","talent"]].

Note that the similarity relation is not transitive. For example, if "great" and "fine" are similar, and "fine" and "good" are similar, "great" and "good" are not necessarily similar.

However, similarity is 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"].

Solution

public class Solution {
    /**
     * @param words1: a list of string
     * @param words2: a list of string
     * @param pairs: a list of string pairs
     * @return: return a boolean, denote whether two sentences are similar or not
     */
    public boolean isSentenceSimilarity(String[] words1, String[] words2, List> pairs) {
        // write your code here
        if (words1.length != words2.length) return false;
        Map> map = new HashMap<>();
        for (List pair: pairs) {
            if (!map.containsKey(pair.get(0))) {
                map.put(pair.get(0), new HashSet());
            }
            if (!map.containsKey(pair.get(1))) {
                map.put(pair.get(1), new HashSet());
            }
            map.get(pair.get(0)).add(pair.get(1));
            map.get(pair.get(1)).add(pair.get(0));
        }
        for (int i = 0; i < words1.length; i++) {
            // if (words1[i] == words2[i]) continue;
            if (!map.containsKey(words1[i])) return false;
            if (!map.get(words1[i]).contains(words2[i])) return false;
        }
        return true;
    }
}

GPU云服务器云服务器 Similarity sentence

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/71632.html

【手撕 - 自然语言处理】手撕 TextRank（01）大佬是怎么实现 Python 版的

摘要：开撕文件夹下的程序展示了怎么使用这个版本的。文件行数这句是重点摘要然后，我们知道重点函数是，我们再来看它是怎么工作的。再仔细阅读一遍，原来写这个库的大佬用种不同的方法实现了个函数，请收下我的膝盖。作者：LogM 本文原载于 https://segmentfault.com/u/logm/articles ，不允许转载~ 1. 源码来源 TextRank4ZH 源码：https://g...

JerryC 2019-07-31 11:29 评论0 收藏0
[LeetCode/LintCode] Top K Frequent Words

LeetCode version Problem Given a non-empty list of words, return the k most frequent elements. Your answer should be sorted by frequency from highest to lowest. If two words have the same frequency, t...

0x584a 2019-08-15 13:32 评论0 收藏0
[LeetCode/LintCode] Is Subsequence

Problem Given a string s and a string t, check if s is subsequence of t. You may assume that there is only lower case English letters in both s and t. t is potentially a very long (length ~= 500,000) ...

terasum 2019-08-19 11:05 评论0 收藏0