使字符串总不同字符的数目相等

题目

2531. 使字符串总不同字符的数目相等

---

给你两个下标从 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 <= 10^5
• word1 和 word2 仅由小写英文字母组成。

题解

方法一：

思路

暴力模拟是最简洁的。
如果对给出的字符串分类讨论，我们可以无法一次性全面的想到所有的特殊情况，不如暴力模拟。
就考虑所有可能的交换情况看是否存在可行解即可。

代码

class Solution {
public:
    bool isItPossible(string w1, string w2) {
        map<char,int> a, b;
        for (char i:w1) a[i]++;
        for (char i:w2) b[i]++;
        
        for (auto [i,j]:a) {
            for (auto [x,y]:b) {
                map<char,int> c = a, d = b;
                c[x]++, d[x]--;
                c[i]--, d[i]++;
                int u=0, v=0;
                for (char t='a'; t<'z'; t++) {
                    if (c[t] && !d[t]) u++;
                    if (!c[t] && d[t]) v++;
                }
                if (u==v) return true;
            }
        }
        return false;
    }
};