句子相似性

难度:

标签:

题目描述

代码结果

运行时间: 20 ms, 内存: 16.0 MB

/*
 * 思路：
 * 1. 将句子1和句子2转换为单词数组。
 * 2. 如果两个句子的长度不一致，则它们不能相似。
 * 3. 使用Java Stream API遍历每对对应的单词，检查它们是否相同或在相似对集合中。
 * 4. 如果所有的单词对都满足条件，则句子相似。
 */
import java.util.HashSet;
import java.util.List;
import java.util.Set;
import java.util.stream.IntStream;
 
public class SentenceSimilarityStream {
    public boolean areSentencesSimilar(String[] sentence1, String[] sentence2, List<List<String>> similarPairs) {
        if (sentence1.length != sentence2.length) return false;
        
        Set<String> similarSet = new HashSet<>();
        similarPairs.forEach(pair -> {
            similarSet.add(pair.get(0) + "#" + pair.get(1));
            similarSet.add(pair.get(1) + "#" + pair.get(0));
        });
        
        return IntStream.range(0, sentence1.length)
                        .allMatch(i -> sentence1[i].equals(sentence2[i]) || similarSet.contains(sentence1[i] + "#" + sentence2[i]));
    }
}

解释

方法:

该题解的思路是先判断两个句子的长度是否相等，如果不等则直接返回 False。然后将两个句子中对应位置的单词组成一个pair，遍历所有pairs，对于每个pair，如果两个单词相同，或者该pair在similarPairs中，或者该pair颠倒顺序后在similarPairs中，则认为该pair是similar的。如果所有pairs都满足上述条件，则返回 True，否则返回 False。

时间复杂度:

O(nm)

空间复杂度:

O(n)

代码细节讲解

🦆

在实现时，你如何处理similarPairs中可能存在的重复元素对，或者这种情况不会影响算法的结果？

▷

在逻辑实现中，similarPairs中的重复元素对不会影响算法的结果。算法检查每个单词对是否存在于similarPairs中，重复的元素对只是增加了存储空间的使用，但不会影响结果的正确性。如果对性能和空间有较高要求，可以在处理前将similarPairs转换为一个集合（set），这样可以自动去除重复项，同时查找效率更高。

🦆

为什么选择在遍历pairs时重复检查每个单词对是否相同，而不是一开始就创建一个更有效的数据结构来简化这一过程？

▷

选择在遍历pairs时进行检查的简单性和直接性是一个因素。尽管使用更高效的数据结构（如集合或哈希表）可以提高查找效率，但这会增加代码的复杂性和额外的预处理时间。在数据量不大时，直接遍历和检查可能在性能上足够高效。然而，对于大数据量或高效率要求的情况，确实推荐使用集合或哈希表来存储和快速检查similarPairs。

🦆

算法中提到如果单词对的顺序颠倒后也在similarPairs中算作相似，这是否意味着similarPairs的创建需要包含所有可能的顺序排列？

▷

算法的实现确实暗示了similarPairs应该包含所有可能的顺序，以确保无论单词对的顺序如何，都能正确判断其相似性。在实际应用中，这意味着如果一个单词对被认为是相似的，那么其颠倒顺序的对也应该被包含在similarPairs中。这样可以避免在运行时重复检查两种顺序，提高效率。

🦆

在题解中，如果一个单词对既不相同也不在similarPairs中，就直接返回False。这种方法是否可能导致提前退出而忽略其他可能相似的单词对？

▷

这种方法的确会导致提前退出，但这是算法设计的意图。算法的目标是判断两个句子是否完全相似，即所有对应的单词对都必须是相似的。如果任一对单词不符合相似性要求，整个句子就不可能完全相似，因此提前退出是合适的，这样可以避免不必要的进一步检查，提高算法效率。

相关问题

省份数量

有 n 个城市，其中一些彼此相连，另一些没有相连。如果城市 a 与城市 b 直接相连，且城市 b 与城市 c 直接相连，那么城市 a 与城市 c 间接相连。

省份是一组直接或间接相连的城市，组内不含其他没有相连的城市。

给你一个 n x n 的矩阵 isConnected ，其中 isConnected[i][j] = 1 表示第 i 个城市和第 j 个城市直接相连，而 isConnected[i][j] = 0 表示二者不直接相连。

返回矩阵中省份的数量。

示例 1：

输入：isConnected = [[1,1,0],[1,1,0],[0,0,1]]
输出：2

示例 2：

输入：isConnected = [[1,0,0],[0,1,0],[0,0,1]]
输出：3

提示：

1 <= n <= 200
n == isConnected.length
n == isConnected[i].length
isConnected[i][j] 为 1 或 0
isConnected[i][i] == 1
isConnected[i][j] == isConnected[j][i]

账户合并

给定一个列表 accounts，每个元素 accounts[i] 是一个字符串列表，其中第一个元素 accounts[i][0] 是 名称 (name)，其余元素是 emails 表示该账户的邮箱地址。

现在，我们想合并这些账户。如果两个账户都有一些共同的邮箱地址，则两个账户必定属于同一个人。请注意，即使两个账户具有相同的名称，它们也可能属于不同的人，因为人们可能具有相同的名称。一个人最初可以拥有任意数量的账户，但其所有账户都具有相同的名称。

合并账户后，按以下格式返回账户：每个账户的第一个元素是名称，其余元素是 按字符 ASCII 顺序排列 的邮箱地址。账户本身可以以 任意顺序 返回。

示例 1：

输入：accounts = [["John", "[email protected]", "[email protected]"], ["John", "[email protected]"], ["John", "[email protected]", "[email protected]"], ["Mary", "[email protected]"]]
输出：[["John", '[email protected]', '[email protected]', '[email protected]'],  ["John", "[email protected]"], ["Mary", "[email protected]"]]
解释：
第一个和第三个 John 是同一个人，因为他们有共同的邮箱地址 "[email protected]"。 
第二个 John 和 Mary 是不同的人，因为他们的邮箱地址没有被其他帐户使用。
可以以任何顺序返回这些列表，例如答案 [['Mary'，'[email protected]']，['John'，'[email protected]']，
['John'，'[email protected]'，'[email protected]'，'[email protected]']] 也是正确的。

示例 2：

输入：accounts = [["Gabe","[email protected]","[email protected]","[email protected]"],["Kevin","[email protected]","[email protected]","[email protected]"],["Ethan","[email protected]","[email protected]","[email protected]"],["Hanzo","[email protected]","[email protected]","[email protected]"],["Fern","[email protected]","[email protected]","[email protected]"]]
输出：[["Ethan","[email protected]","[email protected]","[email protected]"],["Gabe","[email protected]","[email protected]","[email protected]"],["Hanzo","[email protected]","[email protected]","[email protected]"],["Kevin","[email protected]","[email protected]","[email protected]"],["Fern","[email protected]","[email protected]","[email protected]"]]

提示：

1 <= accounts.length <= 1000
2 <= accounts[i].length <= 10
1 <= accounts[i][j].length <= 30
accounts[i][0] 由英文字母组成
accounts[i][j] (for j > 0) 是有效的邮箱地址

句子相似性 II

图像渲染小行星碰撞