确定两个字符串是否接近
难度:
标签:
题目描述
代码结果
运行时间: 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)` 方法,而不是遍历字符串一次统计所有字符的次数?
▷🦆
题解中的方法将字典的值排序后比较,这种排序是否是必需的?如果只要字符的出现次数集合相同是否也能认为两个字符串接近?
▷