使字符串中不同字符的数目相等
难度:
标签:
题目描述
You are given two 0-indexed strings word1 and word2.
A move consists of choosing two indices i and j such that 0 <= i < word1.length and 0 <= j < word2.length and swapping word1[i] with word2[j].
Return true if it is possible to get the number of distinct characters in word1 and word2 to be equal with exactly one move. Return false otherwise.
Example 1:
Input: word1 = "ac", word2 = "b" Output: false Explanation: Any pair of swaps would yield two distinct characters in the first string, and one in the second string.
Example 2:
Input: word1 = "abcc", word2 = "aab" Output: true Explanation: We swap index 2 of the first string with index 0 of the second string. The resulting strings are word1 = "abac" and word2 = "cab", which both have 3 distinct characters.
Example 3:
Input: word1 = "abcde", word2 = "fghij" Output: true Explanation: Both resulting strings will have 5 distinct characters, regardless of which indices we swap.
Constraints:
1 <= word1.length, word2.length <= 105word1andword2consist of only lowercase English letters.
代码结果
运行时间: 100 ms, 内存: 16.4 MB
/*
* 思路：
* 1. 使用 Java Stream 计算 word1 和 word2 中不同字符的数量。
* 2. 遍历 word1 和 word2 的所有可能交换情况，检查交换后不同字符的数量是否相等。
* 3. 如果找到满足条件的交换，返回 true；否则返回 false。
*/
import java.util.stream.*;
public class Solution {
public boolean canBeEqualByOneMove(String word1, String word2) {
long unique1 = word1.chars().distinct().count();
long unique2 = word2.chars().distinct().count();
for (int i = 0; i < word1.length(); i++) {
for (int j = 0; j < word2.length(); j++) {
if (word1.charAt(i) == word2.charAt(j)) continue;
String newWord1 = new StringBuilder(word1).replace(i, i + 1, String.valueOf(word2.charAt(j))).toString();
String newWord2 = new StringBuilder(word2).replace(j, j + 1, String.valueOf(word1.charAt(i))).toString();
long newUnique1 = newWord1.chars().distinct().count();
long newUnique2 = newWord2.chars().distinct().count();
if (newUnique1 == newUnique2) return true;
}
}
return false;
}
}
解释
方法:
本题解的思路是通过计算字符串中每个字符的出现次数（使用Counter），然后分析两个字符串中字符的交换是否能使它们变得具有相同数目的不同字符。 核心思想是：
1. 如果两个字符相同，且word1和word2的不同字符数目已经相等，则直接返回True。
2. 如果两个字符不同，通过一个复杂的条件判断来确定交换后是否能达到不同字符数目相等。该条件考虑了交换字符后各自字符串的不同字符数目的变化：
- `(k2 not in count1) - (v1 == 1) + len(count1) == (k1 not in count2) - (v2 == 1) + len(count2)`
这个条件检查交换后两个字符串的不同字符数是否保持平衡。这里，`(k2 not in count1)` 和 `(k1 not in count2)` 检查是否引入了新的字符，而 `(v1 == 1)` 和 `(v2 == 1)` 检查交换的字符是否是唯一的，如果是，则交换后该字符将不再出现在原字符串中。
时间复杂度:
O(n + m)
空间复杂度:
O(1)
代码细节讲解
🦆
在判断条件`(k2 not in count1) - (v1 == 1) + len(count1) == (k1 not in count2) - (v2 == 1) + len(count2)`中，每个部分的逻辑是怎样的？具体来说，`(k2 not in count1) - (v1 == 1)`是如何影响字符串的不同字符数的？
▷🦆
题解中提到如果字符相同并且不同字符的数量已相等则直接返回True，能否详细解释为什么在这种情况下不需要考虑其他字符的交换可能性？
▷🦆
对于复杂的条件判断，是否存在某些特殊情况下会出现逻辑错误或者漏判，例如当两个字符串中的字符完全不同时？
▷