2840.判断通过操作能否让字符串相等 II：字符串排序或哈希表

【LetMeFly】2840.判断通过操作能否让字符串相等 II：字符串排序或哈希表

力扣题目链接：https://leetcode.cn/problems/check-if-strings-can-be-made-equal-with-operations-ii/

给你两个字符串 s1 和 s2 ，两个字符串长度都为 n ，且只包含 小写 英文字母。

你可以对两个字符串中的 任意一个 执行以下操作 任意 次：

• 选择两个下标 i 和 j ，满足 i < j 且 j - i 是 偶数，然后 交换 这个字符串中两个下标对应的字符。

 

如果你可以让字符串 s1 和 s2 相等，那么返回 true ，否则返回 false 。

 

 

示例 1：

输入：s1 = "abcdba", s2 = "cabdab"
输出：true
解释：我们可以对 s1 执行以下操作：
- 选择下标 i = 0 ，j = 2 ，得到字符串 s1 = "cbadba" 。
- 选择下标 i = 2 ，j = 4 ，得到字符串 s1 = "cbbdaa" 。
- 选择下标 i = 1 ，j = 5 ，得到字符串 s1 = "cabdab" = s2 。

示例 2：

输入：s1 = "abe", s2 = "bea"
输出：false
解释：无法让两个字符串相等。

 

提示：

• n == s1.length == s2.length
• 1 <= n <= 105
• s1 和 s2 只包含小写英文字母。

解题思路：奇偶分别判

奇数下标元素可以任意交换，偶数下标也可以任意交换，所以只需要分别看看在所有奇数位置组成的字符串和偶数位置组成的字符串是否等价就好了。

方法一：字符串排序

将奇数位置和偶数位置字符分别摘出来组成临时字符串，排序，看是否相等。

• 时间复杂度$O(n\log n)$
• 空间复杂度$O(n)$

AC代码

C++

/*
 * @LastEditTime: 2026-03-30 09:28:44
 */
class Solution {
public:
    bool checkStrings(const string& s1, const string& s2) {
        int n = s1.size();
        string odd1, odd2, even1, even2;
        odd1.reserve(n / 2);
        odd2.reserve(n / 2);
        even1.reserve(n / 2);
        even2.reserve(n / 2);
        for (int i = 0; i < n; i++) {
            if (i % 2) {
                odd1.push_back(s1[i]);
                odd2.push_back(s2[i]);
            } else {
                even1.push_back(s1[i]);
                even2.push_back(s2[i]);
            }
        }
        sort(odd1.begin(), odd1.end());
        sort(odd2.begin(), odd2.end());
        sort(even1.begin(), even1.end());
        sort(even2.begin(), even2.end());
        return odd1 == odd2 && even1 == even2;
    }
};

方法二：哈希表

哈希表统计两个字符串在奇数位置和偶数位置出现字符次数的diff，若最终哈希表中元素全部为$0$则返回true。

• 时间复杂度$O(n + C)$，其中$C=26$
• 空间复杂度$O(C)$

AC代码

C++

/*
 * @LastEditTime: 2026-03-30 09:32:52
 */
class Solution {
public:
    bool checkStrings(const string& s1, const string& s2) {
        int n = s1.size();
        int cnt[2][26] = {0};
        for (int i = 0; i < n; i++) {
            cnt[i % 2][s1[i] - 'a']++;
            cnt[i % 2][s2[i] - 'a']--;
        }
        
        for (int i = 0; i < 26; i++) {
            if (cnt[0][i] || cnt[1][i]) {
                return false;
            }
        }
        return true;
    }
};

AC,98.21%,100.00%

同步发文于CSDN和我的个人博客，原创不易，转载经作者同意后请附上原文链接哦~

千篇源码题解已开源