原文链接: https://leetcode-cn.com/problems/determine-if-two-strings-are-close
英文原文
Two strings are considered close if you can attain one from the other using the following operations:
- Operation 1: Swap any two existing characters.
<ul> <li>For example, <code>a<u>b</u>cd<u>e</u> -> a<u>e</u>cd<u>b</u></code></li> </ul> </li> <li>Operation 2: Transform <strong>every</strong> occurrence of one <strong>existing</strong> character into another <strong>existing</strong> character, and do the same with the other character. <ul> <li>For example, <code><u>aa</u>c<u>abb</u> -> <u>bb</u>c<u>baa</u></code> (all <code>a</code>'s turn into <code>b</code>'s, and all <code>b</code>'s turn into <code>a</code>'s)</li> </ul> </li>
You can use the operations on either string as many times as necessary.
Given two strings, word1 and word2, return true if word1 and word2 are close, 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: "abc" -> "acb" Apply Operation 1: "acb" -> "bca"
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: "cabbba" -> "caabbb"
Apply Operation 2: "caabbb" -> "baaccc"
Apply Operation 2: "baaccc" -> "abbccc"
Example 4:
Input: word1 = "cabbba", word2 = "aabbss" Output: false Explanation: It is impossible to attain word2 from word1, or vice versa, in any amount of operations.
Constraints:
1 <= word1.length, word2.length <= 105word1andword2contain only lowercase English letters.
中文题目
如果可以使用以下操作从一个字符串得到另一个字符串，则认为两个字符串 接近 ：
- 操作 1：交换任意两个 现有 字符。
<ul> <li>例如，<code>a<strong>b</strong>cd<strong>e</strong> -> a<strong>e</strong>cd<strong>b</strong></code></li> </ul> </li> <li>操作 2：将一个 <strong>现有</strong> 字符的每次出现转换为另一个 <strong>现有</strong> 字符，并对另一个字符执行相同的操作。 <ul> <li>例如，<code><strong>aa</strong>c<strong>abb</strong> -> <strong>bb</strong>c<strong>baa</strong></code>（所有 <code>a</code> 转化为 <code>b</code> ，而所有的 <code>b</code> 转换为 <code>a</code> ）</li> </ul> </li>
你可以根据需要对任意一个字符串多次使用这两种操作。
给你两个字符串，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"
示例 4：
输入：word1 = "cabbba", word2 = "aabbss" 输出：false 解释：不管执行多少次操作，都无法从 word1 得到 word2 ，反之亦然。
提示：
1 <= word1.length, word2.length <= 105word1和word2仅包含小写英文字母
通过代码
高赞题解
解题思路
把题目要求翻译成人话就是，
如果两个字符串：
- 包含的字符种类完全一样；
- 把各个字符的重复次数放在一个数组里，数组在排序后完全一样；
那么这两个字符串接近。
所以：
- 如果两个字符串长度不一样，那么直接返回
false； - 遍历两个字符串，用两个长度 $26$ 的数组存放次数；
- 同时遍历这两个数组，如果在某下标 $i$ 处出现一个是 $0$ 一个不是 $0$（即异或结果是 $1$）的情况，那么直接返回
false； - 排序后如果数组不相同，也返回
false； - 否则返回
true。
代码
[]class Solution { public: bool closeStrings(string word1, string word2) { int m = word1.size(); int n = word2.size(); if (m != n) return false; vector<int> repeat1(26, 0), repeat2(26, 0); for (int i = 0; i < m; ++i) { ++repeat1[word1[i] - 'a']; ++repeat2[word2[i] - 'a']; } for (int i = 0; i < 26; ++i) if ((repeat1[i] == 0) ^ (repeat2[i] == 0)) return false; sort(repeat1.begin(), repeat1.end()); sort(repeat2.begin(), repeat2.end()); for (int i = 0; i < 26; ++i) if (repeat1[i] != repeat2[i]) return false; return true; } };
时空复杂度
- 时间复杂度 ：$O(n)$，$n$ 是字符串的长度。虽然我们使用了排序，但是待排数组是个长度为 $26$ 的定长数组，对它进行遍历和排序的时间代价都是常数级的。
- 空间复杂度：$O(1)$，算法只使用了常数级的空间。虽然我们使用了排序，但是由于数组长度永远不变，其空间代价依然是常数级的。
统计信息
| 通过次数 | 提交次数 | AC比率 |
|---|---|---|
| 5695 | 12251 | 46.5% |
提交历史
| 提交时间 | 提交结果 | 执行时间 | 内存消耗 | 语言 |
|---|
