LeetCode 1657. 确定两个字符串是否接近：思维题

本文介绍: Le e tCode 1657. 确定两个字符串是否接近：思维题如果可以使用以下操作从一个字符串得到另一个字符串，则认为两个字符串接近：操作 1：交换任意两个现有字符。例如，abc de -&g t; ae cdb操作 2：将一个现有字符的每次出现转换为另一个现有字符，并对另一个字符执行相同的操作。例如，a a ca b b -&g t; b b cba a（所有 a 转化为 b ，而所有的 b 转换为 a ）你可以根据需要对任意一个字符串多次使用这两种操作。给你两个字符串，word1 和 word2 。如果

【Le tMeFly】1657.确定两个 字符串 是否接近：思维题

力扣题目链接：https://leetcode.cn/problems/determine-if-two-strings-are-close/

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

操作 1：交换任意两个现有字符。

&lt;ul&gt;
	&lt;li&gt;例如，&lt;code&gt;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 <= 10⁵
word1 和 word2 仅包含小写英文字母

方法一：思维题

思路：

首先要保证两个字符串出现的字符相同（不能一个出现了a一个没出现过a）。

之后，假设字符串1的前26个字母分别出现了1次、0次、3次、5次、0次、0次、…，字符串2的前26个字母分别出现了3次、5次、1次、0次、0次、…，（sorted[1, 3, 5] = sorted[3, 5, 1]），则二者“接近”。

因为就像冒泡排序一样两两交换，总能换为对应字母出现次数相同。

方法：

开辟两个大小为26的数组，记录两个字符串中每个字符出现的次数。

判断两个数组的“为0非0”情况是否相同
判断两个数组排序后是否相等

若满足条件则返回true。

AC代码

C++

class Solution {
public:
    bool closeStrings(string word1, string word2) {
        int bin1[26] = {0}, bin2[26] = {0};
        for (char c : word1) {
            bin1[c - 'a']++;
        }
        for (char c : word2) {
            bin2[c - 'a']++;
        }
        for (int i = 0; i < 26; i++) {
            if ((bin1[i] || 0) != (bin2[i] || 0)) {
                return false;
            }
        }
        sort(bin1, bin1 + 26);
        sort(bin2, bin2 + 26);
        for (int i = 0; i < 26; i++) {
            if (bin1[i] != bin2[i]) {
                return false;
            }
        }
        return true;
    }
};

Python

class Solution:
    def closeStrings(self, word1: str, word2: str) -> bool:
        bin1 = [0] * 26
        bin2 = [0] * 26
        for c in word1:
            bin1[ord(c) - ord('a')] += 1
        for c in word2:
            bin2[ord(c) - ord('a')] += 1
        for i in range(26):
            if (bin1[i] == 0) != (bin2[i] == 0):
                return False
        bin1.sort()
        bin2.sort()
        return bin1 == bin2