LWC 60:734. Sentence Similarity

LWC 60:734. Sentence Similarity

传送门:734. Sentence Similarity

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”].

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].

思路: 查询每个单词是否有对应的近义词,如果找不到则返回false。

Java版:

    public boolean areSentencesSimilar(String[] words1, String[] words2, String[][] pairs) {
        if (words1.length != words2.length) return false;
        Map<String, Set<String>> map = new HashMap<>();
        for (String[] p : pairs) {
            map.computeIfAbsent(p[0], k -> new HashSet<>()).add(p[1]);
        }

        for (int i = 0; i < words1.length; ++i) {
            String a = words1[i];
            String b = words2[i];
            if (!a.equals(b)) {
                if (!map.getOrDefault(a, new HashSet<>()).contains(b) && !map.getOrDefault(b, new HashSet<>()).contains(a)) return false;
            }
        }
        return true;
    }

Python版:

    def areSentencesSimilar(self, words1, words2, pairs):
        """
        :type words1: List[str]
        :type words2: List[str]
        :type pairs: List[List[str]]
        :rtype: bool
        """
        from collections import  defaultdict
        n1 = len(words1)
        n2 = len(words2)

        if n1 != n2:
            return False

        map = defaultdict(set)
        for word1, word2 in pairs:
            map[word1].add(word2)
        for word1, word2 in zip(words1, words2):
            if word1 != word2 and word2 not in map[word1] and word1 not in map[word2]:
                return False
        return True

Python 注意 all 的使用:

all([…]) or all((…)) 所有元素不为空,不为0,不为Flase,则返回True

    def areSentencesSimilar(self, words1, words2, pairs):
        """
        :type words1: List[str]
        :type words2: List[str]
        :type pairs: List[List[str]]
        :rtype: bool
        """
        from collections import  defaultdict
        n1 = len(words1)
        n2 = len(words2)

        if n1 != n2:
            return False

        map = defaultdict(set)
        for w in words1:
            map[w].add(w)

        for w in words2:
            map[w].add(w)

        for word1, word2 in pairs:
            map[word1].add(word2)
            map[word2].add(word1)
        return all(b in map[a] for a, b in zip(words1, words2))     

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏Android知识点总结

Java容器源码攻坚战--第二战:ArrayList

812
来自专栏cmazxiaoma的架构师之路

Java数据结构和算法(1)--自定义一个数组类和动态数组类

1194
来自专栏格子的个人博客

Java源码阅读之ArrayList - JDK1.8

当你对某件事情很感兴趣的时候,时间的流逝在感知中都模糊了(是不是很文艺,绕口得都快听不懂了),通俗来说,就是时间过得很快。

815
来自专栏计算机视觉与深度学习基础

Leetcode 124 Binary Tree Maximum Path Sum

Given a binary tree, find the maximum path sum. For this problem, a path is de...

1949
来自专栏机器学习与自然语言处理

04-树6. Huffman Codes--优先队列(堆)在哈夫曼树与哈夫曼编码上的应用

题目来源:http://www.patest.cn/contests/mooc-ds/04-%E6%A0%916 In 1953, David A. Huffm...

1857
来自专栏King_3的技术专栏

leetcode-744-Find Smallest Letter Greater Than Target(改进的二分查找)

2257
来自专栏令仔很忙

集合详解(二)----ArrayList源代码剖析(JDK1.7)

ArrayList是List类的一个典型的实现,是基于数组实现的List类,因此,ArrayList封装了一个动态的、可变长度的Object[]数组。Arra...

481
来自专栏开发 & 算法杂谈

PAT Advanced 1005

Given a non-negative integer N, your task is to compute the sum of all the digi...

702
来自专栏机器学习入门

LWC 60:736. Parse Lisp Expression

LWC 60:736. Parse Lisp Expression 传送门:736. Parse Lisp Expression Problem: You a...

1687
来自专栏ml

HDUOJ---The Moving Points

The Moving Points Time Limit: 6000/3000 MS (Java/Others)    Memory Limit: 32768/...

3114

扫码关注云+社区