1657. 确定两个字符串是否接近

🟠   🔖  哈希表 字符串 计数 排序  🔗 力扣 LeetCode

题目

Two strings are considered close if you can attain one from the other using the following operations:

• Operation 1: Swap any two existing characters.
• For example, a _b_ cd _e_ -> a _e_ cd _b_
• Operation 2: Transform every occurrence of one existing character into another existing character, and do the same with the other character.
• For example, _aa_ c _abb_ -> _bb_ c _baa_ (all a's turn into b's, and all b's turn into a's)

You can use the operations on either string as many times as necessary.

Given two strings, word1 and word2, return true ifword1 andword2 _areclose , and _false otherwise.

Example 1:

Input: word1 = "abc", word2 = "bca"

Output: true

Explanation: You can attain word2 from word1 in 2 operations.

Apply Operation 1: "a bc " -> "a cb "

Apply Operation 1: "a c b " -> "b c a "

Example 2:

Input: word1 = "a", word2 = "aa"

Output: false

Explanation: It is impossible to attain word2 from word1, or vice versa, in any number of operations.

Example 3:

Input: word1 = "cabbba", word2 = "abbccc"

Output: true

Explanation: You can attain word2 from word1 in 3 operations.

Apply Operation 1: "ca b bb a " -> "ca a bb b "

Apply Operation 2: "c aa bbb " -> "b aa ccc "

Apply Operation 2: "baa ccc" -> "abb ccc"

Constraints:

• 1 <= word1.length, word2.length <= 10^5
• word1 and word2 contain only lowercase English letters.

题目大意

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

• 操作 1：交换任意两个 现有 字符。
  • 例如，a _b_ cd _e_ -> a _e_ cd _b_
• 操作 2：将一个 现有 字符的每次出现转换为另一个 现有 字符，并对另一个字符执行相同的操作。
  • 例如， _aa_ c _abb_ -> _bb_ c _baa_（所有 a 转化为 b ，而所有的 b 转换为 a ）

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

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

示例 1：

输入： word1 = "abc", word2 = "bca"

输出： true

解释： 2 次操作从 word1 获得 word2 。

执行操作 1："a bc " -> "a cb "

执行操作 1："a c b " -> "b c a "

示例 2：

输入： word1 = "a", word2 = "aa"

输出： false

解释： 不管执行多少次操作，都无法从 word1 得到 word2 ，反之亦然。

示例 3：

输入： word1 = "cabbba", word2 = "abbccc"

输出： true

解释： 3 次操作从 word1 获得 word2 。

执行操作 1："ca b bb a " -> "ca a bb b "

执行操作 2："c aa bbb " -> "b aa ccc "

执行操作 2："baa ccc" -> "abb ccc"

提示：

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

解题思路

1. 长度检查：

   • 首先检查 word1 和 word2 的长度。如果它们的长度不同，则直接返回 false。

2. 字符统计：

   • 定义一个辅助函数 count(str) 来统计字符串中每个字符的出现次数。
   • 使用 Map 来存储字符及其对应的出现次数。
   • 在统计时，遍历字符串中的每个字符，将其添加到 Map 中，并更新其计数。

3. 生成唯一标识：

   • 在 count 函数中，将 Map 的键（字符）和对应的值（出现次数）分别提取出来，并进行排序。
   • 将字符和频率数组转换为以逗号分隔的字符串，作为唯一标识。

4. 比较结果：

   • 调用 count 函数分别对 word1 和 word2 进行统计，并比较它们的字符和频率标识。如果两者相同，返回 true；否则返回 false。

复杂度分析

• 时间复杂度：O(n)，其中 n 是字符串的长度，统计字符的时间是 O(n)。虽然在排序字符和频率时，每次操作都是 O(m log m)，其中 m 是不同字符的数量，但是由于字符集有限（假设最多有 26 个小写字母），这在实际情况下是常数级别的，因此整体复杂度近似为 O(n)。

• 空间复杂度：O(1)，在最坏的情况下，可能需要存储所有字符及其出现次数，空间复杂度取决于字符集的大小，但仍然是常数级别。

代码

/**
 * @param {string} word1
 * @param {string} word2
 * @return {boolean}
 */
var closeStrings = function (word1, word2) {
	if (word1.length !== word2.length) return false;
	const count = (str) => {
		let map = new Map();
		for (let char of str) {
			map.set(char, (map.get(char) || 0) + 1);
		}
		return [...map.keys(), ...map.values()].sort().join(',');
	};
	return count(word1) == count(word2);
};

相关题目

题号	标题	题解	标签	难度
859	亲密字符串		哈希表 字符串
1247	交换字符使得字符串相同		贪心 数学 字符串
1347	制造字母异位词的最小步骤数		哈希表 字符串 计数