LeetCode 题解工作台
使字符串中不同字符的数目相等
给你两个下标从 0 开始的字符串 word1 和 word2 。 一次 移动 由以下两个步骤组成： 选中两个下标 i 和 j ，分别满足 0 和 0 ， 交换 word1[i] 和 word2[j] 。 如果可以通过 恰好一次 移动，使 word1 和 word2 中不同字符的数目相等，则返回 tr…
3
题型
5
代码语言
3
相关题
当前训练重点
中等 · 哈希·表·结合·string
答案摘要
我们先用两个长度为 的数组 和 分别记录字符串 和 中每个字符的出现次数。 然后我们分别统计 和 中不同字符的个数，分别记为 和 。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 哈希·表·结合·string 题型思路
题目描述
给你两个下标从 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 <= 105word1和word2仅由小写英文字母组成。
解题思路
方法一：计数 + 枚举
我们先用两个长度为 的数组 和 分别记录字符串 和 中每个字符的出现次数。
然后我们分别统计 和 中不同字符的个数，分别记为 和 。
接下来我们枚举 中的每个字符 和 中的每个字符 ，如果 ，那么我们只需要判断 和 是否相等；否则，我们需要判断 和 是否相等。如果相等，那么我们就找到了一种方案，返回 。
如果我们枚举完所有的字符都没有找到合适的方案，那么我们就返回 。
时间复杂度 ，其中 和 分别是字符串 和 的长度，而 是字符集，本题中字符集为小写字母，所以 。
class Solution:
def isItPossible(self, word1: str, word2: str) -> bool:
cnt1 = Counter(word1)
cnt2 = Counter(word2)
x, y = len(cnt1), len(cnt2)
for c1, v1 in cnt1.items():
for c2, v2 in cnt2.items():
if c1 == c2:
if x == y:
return True
else:
a = x - (v1 == 1) + (cnt1[c2] == 0)
b = y - (v2 == 1) + (cnt2[c1] == 0)
if a == b:
return True
return False
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity depends on the number of unique characters in each string, typically O(26*26) due to limited lowercase letters, and space complexity is O(26) per string for frequency maps. |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Pay attention to edge cases where one string has only duplicates.
- question_mark
Watch for off-by-one errors when counting distinct characters after a swap.
- question_mark
Consider how swapping identical characters affects distinct counts.
常见陷阱
外企场景- error
Assuming any swap will work without checking distinct counts.
- error
Failing to handle swaps involving characters already present in both strings.
- error
Overlooking the need to update counts after each simulated swap.
进阶变体
外企场景- arrow_right_alt
Allow multiple swaps to equalize distinct characters instead of exactly one.
- arrow_right_alt
Limit swaps to adjacent characters only and evaluate feasibility.
- arrow_right_alt
Consider uppercase and lowercase letters, increasing the character set size.