使字符串中不同字符的数目相等

标签: 哈希表 字符串 计数

难度: Medium

给你两个下标从 0 开始的字符串 word1 和 word2 。

一次 移动 由以下两个步骤组成：

  • 选中两个下标 i 和 j ，分别满足 0 <= i < word1.length 和 0 <= j < word2.length ，
  • 交换 word1[i] 和 word2[j] 。

如果可以通过 恰好一次 移动，使 word1 和 word2 中不同字符的数目相等，则返回 true ；否则，返回 false 。

示例 1：

输入：word1 = "ac", word2 = "b"
输出：false
解释：交换任何一组下标都会导致第一个字符串中有 2 个不同的字符，而在第二个字符串中只有 1 个不同字符。

示例 2：

输入：word1 = "abcc", word2 = "aab"
输出：true
解释：交换第一个字符串的下标 2 和第二个字符串的下标 0 。之后得到 word1 = "abac" 和 word2 = "cab" ，各有 3 个不同字符。

示例 3：

输入：word1 = "abcde", word2 = "fghij"
输出：true
解释：无论交换哪一组下标，两个字符串中都会有 5 个不同字符。

提示：

  • 1 <= word1.length, word2.length <= 105
  • word1 和 word2 仅由小写英文字母组成。

Submission

运行时间: 100 ms

内存: 16.4 MB

class Solution:
    def isItPossible(self, word1: str, word2: str) -> bool:
        count1 = Counter(word1)
        count2 = Counter(word2)
        for k1, v1 in count1.items():
            for k2, v2 in count2.items():
                if k1 == k2:
                    if len(count1) == len(count2):
                        return True
                else:
                    if (k2 not in count1) - (v1 == 1) + len(count1) == \
                        (k1 not in count2) - (v2 == 1) + len(count2):
                        return True
        return False

Explain

本题解的思路是通过计算字符串中每个字符的出现次数（使用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)

class Solution:
    def isItPossible(self, word1: str, word2: str) -> bool:
        count1 = Counter(word1)  # 计数word1中每个字符的出现次数
        count2 = Counter(word2)  # 计数word2中每个字符的出现次数
        for k1, v1 in count1.items():
            for k2, v2 in count2.items():
                if k1 == k2:
                    if len(count1) == len(count2):
                        return True  # 如果字符相同并且不同字符的数量已相等
                else:
                    # 如果字符不同，检查通过一次交换是否能使不同字符的数量相等
                    if (k2 not in count1) - (v1 == 1) + len(count1) == \
                        (k1 not in count2) - (v2 == 1) + len(count2):
                        return True
        return False

Explore

在这个条件中，`(k2 not in count1) - (v1 == 1)` 表示交换字符k1和k2后word1的不同字符数目的变化。如果`k2`原本不在`word1`中，那么`k2 not in count1`为1，表示交换后word1将增加一个新字符。如果`v1 == 1`为真，即k1在word1中只出现一次，那么交换后这个字符将会从word1中消失，所以`(v1 == 1)`为1，这意味着不同字符的数量将减少一个。最终，`len(count1)`是交换前word1中不同字符的总数。因此，`(k2 not in count1) - (v1 == 1) + len(count1)`计算了交换后word1的不同字符数目。

如果在两个字符串中找到相同的字符，并且这两个字符串已经有相等数量的不同字符，那么这两个字符串已经满足题目的要求，即不同字符的数目相等。因此，不需要通过交换任何其他字符来尝试修改字符的数量或种类。已经达成的平衡状态意味着任何进一步的交换都是多余的，因为目标已经被满足。

是的，如果两个字符串中的字符完全不相同，那么题解中的逻辑可能会遇到问题。在这种情况下，每个字符都需要找到一个对应的字符进行交换，以尝试平衡不同字符的数量。如果每个字符都是唯一的，那么`(k2 not in count1)`和`(k1 not in count2)`始终为1，而`(v1 == 1)`和`(v2 == 1)`可能也为1（如果每种字符只出现一次）。这种情况下，条件判断可能无法正确处理所有字符的唯一性和独立性，从而导致逻辑错误或漏判。正确的处理需要更细致的逻辑来确保即使在字符完全不同时，也能正确评估和处理不同字符数量的平衡。