[LeetCode/LintCode] Sentence Similarity

dreamtecher 發布于2019-08-16 12:44 / 2872人閱讀

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

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/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