leetcode
leetcode 1501 ~ 1550
确定两个字符串是否接近

确定两个字符串是否接近

难度:

标签:

题目描述

代码结果

运行时间: 64 ms, 内存: 17.2 MB


/*
 * 思路:
 * 1. 首先检查两个字符串长度是否相等,不相等则直接返回 false。
 * 2. 统计两个字符串中每个字符的出现频率。
 * 3. 检查两个字符串是否包含相同的字符集。
 * 4. 检查两个字符串的字符频率分布是否相同。
 */
import java.util.stream.Collectors;
import java.util.stream.IntStream;

public class CloseStringsStream {
    public boolean closeStrings(String word1, String word2) {
        if (word1.length() != word2.length()) return false;
        int[] freq1 = word1.chars().map(c -> c - 'a').collect(
            () -> new int[26], (arr, i) -> arr[i]++, (arr1, arr2) -> IntStream.range(0, arr1.length).forEach(i -> arr1[i] += arr2[i])
        );
        int[] freq2 = word2.chars().map(c -> c - 'a').collect(
            () -> new int[26], (arr, i) -> arr[i]++, (arr1, arr2) -> IntStream.range(0, arr1.length).forEach(i -> arr1[i] += arr2[i])
        );
        return IntStream.range(0, 26).allMatch(i -> freq1[i] == freq2[i] || (freq1[i] == 0 || freq2[i] == 0)) &&
               IntStream.of(freq1).sorted().boxed().collect(Collectors.toList()).equals(
                   IntStream.of(freq2).sorted().boxed().collect(Collectors.toList())
               );
    }
}

解释

方法:

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

时间复杂度:

O(n)

空间复杂度:

O(m)

代码细节讲解

🦆
题解中提到,如果两个字符串的字符集不相同,则直接返回 false。请问为什么字符集必须相同才能认为两个字符串可能接近?
如果两个字符串的字符集不相同,即意味着至少有一个字符在一个字符串中出现而在另一个字符串中没有出现。由于字符串接近的定义要求我们通过重新排列字符频率来使两个字符串接近,如果字符本身不存在于另一个字符串中,那么无论如何交换字符频率,也无法使两个字符串相等。因此,字符集必须完全相同,才有可能通过交换字符频率使两个字符串接近。
🦆
在使用字典存储每个字符的出现次数时,为什么选择了使用 `word1.count(char)` 和 `word2.count(char)` 方法,而不是遍历字符串一次统计所有字符的次数?
在题解中使用 `word1.count(char)` 和 `word2.count(char)` 方法的确不是最优的选择,因为每次调用 count 方法都会遍历整个字符串来计算特定字符的出现次数,这使得时间复杂度上升到 O(n^2),其中 n 是字符串的长度。更高效的方法是遍历每个字符串一次,使用字典来统计每个字符的出现次数,这可以将时间复杂度降低到 O(n)。选择 count 方法可能是出于代码简洁性的考虑,但在性能要求较高的情况下,应该避免使用它。
🦆
题解中的方法将字典的值排序后比较,这种排序是否是必需的?如果只要字符的出现次数集合相同是否也能认为两个字符串接近?
题解中将字典的值(字符频率)排序后比较是必需的,因为仅仅字符的出现次数集合相同并不足以确保两个字符串可以通过重新排列字符频率来接近。例如,如果字符串 `aabb` 和 `abab` 的字符频率集合相同(两个字符出现两次),但它们的具体排列顺序不同,即使字符集相同也不能通过简单的频率重新排列使两个字符串相等。正确的方法是,比较排序后的频率列表,这样可以确保每种字符频率的排列顺序也相同,从而可以通过字符交换使两个字符串接近。

相关问题