确定两个字符串是否接近

标签: 哈希表 字符串 计数 排序

难度: Medium

如果可以使用以下操作从一个字符串得到另一个字符串，则认为两个字符串 接近 ：

  • 操作 1：交换任意两个 现有 字符。
    • 例如，abcde -> aecdb
  • 操作 2：将一个 现有 字符的每次出现转换为另一个 现有 字符，并对另一个字符执行相同的操作。
    • 例如，aacabb -> bbcbaa（所有 a 转化为 b ，而所有的 b 转换为 a ）

你可以根据需要对任意一个字符串多次使用这两种操作。

给你两个字符串，word1 和 word2 。如果 word1 和 word2 接近 ，就返回 true ；否则，返回 false 。

示例 1：

输入：word1 = "abc", word2 = "bca"
输出：true
解释：2 次操作从 word1 获得 word2 。
执行操作 1："abc" -> "acb"
执行操作 1："acb" -> "bca"

示例 2：

输入：word1 = "a", word2 = "aa"
输出：false
解释：不管执行多少次操作，都无法从 word1 得到 word2 ，反之亦然。

示例 3：

输入：word1 = "cabbba", word2 = "abbccc"
输出：true
解释：3 次操作从 word1 获得 word2 。
执行操作 1："cabbba" -> "caabbb"
执行操作 2："caabbb" -> "baaccc"
执行操作 2："baaccc" -> "abbccc"

提示：

  • 1 <= word1.length, word2.length <= 105
  • word1 和 word2 仅包含小写英文字母

Submission

运行时间: 64 ms

内存: 17.2 MB

class Solution:
    def closeStrings(self, word1: str, word2: str) -> bool:
        if(len(word1)!=len(word2)):
            return False
    
        set1=set(word1)
        set2=set(word2)
    
        
        if(set1!=set2):
            return False
        
        
        d1={}
        for i in set1:
            d1[i]=word1.count(i)
            
        d2={}
            
        for i in set2:
            d2[i]=word2.count(i)
            
            
    
        d1=sorted(d1.values())
        d2=sorted(d2.values())
        print(d1)
        print(d2)
            
        
        return d1==d2

Explain

首先，检查两个字符串长度是否相等。如果不相等，直接返回 false。然后，使用集合检查两个字符串是否包含相同的字符集。如果字符集不相同，也返回 false。接下来，计算每个字符在两个字符串中的出现次数，并将这些次数存储在两个字典中。最后，比较这两个字典中的值（已排序）是否相等。如果这些值相等，说明可以通过字符交换得到相同的字符频率，从而可以通过指定的操作使两个字符串接近。

时间复杂度: O(n)

空间复杂度: O(m)

class Solution:
    def closeStrings(self, word1: str, word2: str) -> bool:
        if len(word1) != len(word2):
            return False

        set1 = set(word1)
        set2 = set(word2)
        
        if set1 != set2:
            return False
        
        d1 = {}
        for char in set1:
            d1[char] = word1.count(char)
        
        d2 = {}
        for char in set2:
            d2[char] = word2.count(char)
        
        values1 = sorted(d1.values())
        values2 = sorted(d2.values())
        
        return values1 == values2

Explore

如果两个字符串的字符集不相同，即意味着至少有一个字符在一个字符串中出现而在另一个字符串中没有出现。由于字符串接近的定义要求我们通过重新排列字符频率来使两个字符串接近，如果字符本身不存在于另一个字符串中，那么无论如何交换字符频率，也无法使两个字符串相等。因此，字符集必须完全相同，才有可能通过交换字符频率使两个字符串接近。

在题解中使用 `word1.count(char)` 和 `word2.count(char)` 方法的确不是最优的选择，因为每次调用 count 方法都会遍历整个字符串来计算特定字符的出现次数，这使得时间复杂度上升到 O(n^2)，其中 n 是字符串的长度。更高效的方法是遍历每个字符串一次，使用字典来统计每个字符的出现次数，这可以将时间复杂度降低到 O(n)。选择 count 方法可能是出于代码简洁性的考虑，但在性能要求较高的情况下，应该避免使用它。

题解中将字典的值（字符频率）排序后比较是必需的，因为仅仅字符的出现次数集合相同并不足以确保两个字符串可以通过重新排列字符频率来接近。例如，如果字符串 `aabb` 和 `abab` 的字符频率集合相同（两个字符出现两次），但它们的具体排列顺序不同，即使字符集相同也不能通过简单的频率重新排列使两个字符串相等。正确的方法是，比较排序后的频率列表，这样可以确保每种字符频率的排列顺序也相同，从而可以通过字符交换使两个字符串接近。