What does 'Determine if Two Strings Are Close' mean in algorithm terms?

It means checking if you can transform one string into the other using unlimited swaps and character frequency substitutions, focusing on hash table frequency patterns.

Why compare sorted frequency values instead of raw counts?

Sorting allows you to match frequency distributions without caring about which specific letters hold each count, aligning with allowed transformations.

Does the order of letters in the strings matter?

No, Operation 1 permits free reordering, so only character presence and counts influence closeness.

Can strings with different lengths ever be close?

No, strings must be of equal length to allow transformations; differing lengths immediately return false.

Is a hash table always required for this problem?

While not strictly required, hash tables make counting and comparing character frequencies efficient and clear, matching the Hash Table plus String pattern.

#1657

Medium

auto_awesome哈希·表·结合·string

LeetCode 题解工作台

确定两个字符串是否接近

如果可以使用以下操作从一个字符串得到另一个字符串，则认为两个字符串接近：操作 1：交换任意两个现有字符。例如， a b cd e -> a e cd b 操作 2：将一个现有字符的每次出现转换为另一个现有字符，并对另一个字符执行相同的操作。例如， aa c abb -> bb …

哈希表字符串排序计数

题目描述

如果可以使用以下操作从一个字符串得到另一个字符串，则认为两个字符串接近：

操作 1：交换任意两个现有字符。
- 例如，abcde -> aecdb
操作 2：将一个现有字符的每次出现转换为另一个现有字符，并对另一个字符执行相同的操作。
- 例如，aacabb -> bbcbaa（所有 a 转化为 b ，而所有的 b 转换为 a ）

你可以根据需要对任意一个字符串多次使用这两种操作。

给你两个字符串，word1 和 word2 。如果 word1 和 word2 接近，就返回 true ；否则，返回 false 。

示例 1：

输入：word1 = "abc", word2 = "bca"
输出：true
解释：2 次操作从 word1 获得 word2 。
执行操作 1："abc" -> "acb"
执行操作 1："acb" -> "bca"

示例 2：

输入：word1 = "a", word2 = "aa"
输出：false
解释：不管执行多少次操作，都无法从 word1 得到 word2 ，反之亦然。

示例 3：

输入：word1 = "cabbba", word2 = "abbccc"
输出：true
解释：3 次操作从 word1 获得 word2 。
执行操作 1："cabbba" -> "caabbb"
执行操作 2："caabbb" -> "baaccc"
执行操作 2："baaccc" -> "abbccc"

提示：

1 <= word1.length, word2.length <= 10⁵
word1 和 word2 仅包含小写英文字母

lightbulb

解题思路

方法一：计数 + 排序

根据题目描述，两个字符串接近，需要同时满足以下两个条件：

字符串 word1 和 word2 包含的字母种类必须相同；
将字符串 word1 和 word2 的所有字符出现次数排序，得到的两个数组必须相同。

因此，我们可以先用数组或哈希表分别统计 word1 和 word2 中每种字母出现的次数，然后比较两者是否相同，不相同则提前返回 false。

否则，我们将对应的次数排序，然后依次比较对应位置的两个次数是否相同，不同则返回 false。

遍历结束，返回 true。

时间复杂度 $O(m + n + C \times \log C)$ ，空间复杂度 $O(C)$ 。其中 $m$ 和 $n$ 分别为字符串 word1 和 word2 的长度，而 $C$ 是字母种类。本题中 $C=26$ 。

1

2

3

4

5

6

7

class Solution:
    def closeStrings(self, word1: str, word2: str) -> bool:
        cnt1, cnt2 = Counter(word1), Counter(word2)
        return sorted(cnt1.values()) == sorted(cnt2.values()) and set(
            cnt1.keys()
        ) == set(cnt2.keys())

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Check if both strings contain exactly the same set of letters.
question_mark
Consider if the character frequency distributions are compatible.
question_mark
Watch out for edge cases with repeated single letters or mismatched lengths.

warning

常见陷阱

外企场景

error
Assuming order of letters matters; Operation 1 allows free reordering.
error
Ignoring letters that exist in one string but not the other.
error
Comparing raw frequency dictionaries without sorting the values.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Determine closeness when strings include uppercase letters or digits.
arrow_right_alt
Compute minimal number of operations needed to make strings close.
arrow_right_alt
Check closeness under limited number of allowed swaps or transformations.

help

常见问题

外企场景

继续练习

#1366 通过投票对团队排名 #767 重构字符串 #692 前K个高频单词