2840-判断通过操作能否让字符串相等 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 只包含小写英文字母。

请看 视频讲解 。

有一个更强的结论：改成 j-i=2，也是一样的。

既然可以交换相距为 2 的字符，那么相距为 4 的字符可以通过多次交换实现。例如 x-y-z 变成 y-x-z 变成 y-z-x 变成 z-y-z。

依此类推，所有相距为偶数的字符都可以随意交换。

所以只需要看下标为偶数的字符个数是否都一样，下标为奇数的字符个数是否都一样。

[sol-Python3]

class Solution:
    def canBeEqual(self, s1: str, s2: str) -> bool:
        return Counter(s1[::2]) == Counter(s2[::2]) and Counter(s1[1::2]) == Counter(s2[1::2])

[sol-Java]

class Solution {
    public boolean canBeEqual(String s1, String s2) {
        var cnt1 = new int[2][26];
        var cnt2 = new int[2][26];
        for (int i = 0; i < s1.length(); i++) {
            cnt1[i % 2][s1.charAt(i) - 'a']++;
            cnt2[i % 2][s2.charAt(i) - 'a']++;
        }
        return Arrays.deepEquals(cnt1, cnt2);
    }
}

[sol-C++]

class Solution {
public:
    bool canBeEqual(string s1, string s2) {
        int cnt1[2][26]{}, cnt2[2][26]{};
        for (int i = 0; i < s1.length(); i++) {
            cnt1[i % 2][s1[i] - 'a']++;
            cnt2[i % 2][s2[i] - 'a']++;
        }
        return memcmp(cnt1, cnt2, sizeof(cnt1)) == 0;
    }
};

[sol-Go]

func canBeEqual(s1, s2 string) bool {
	var cnt1, cnt2 [2][26]int
	for i, c := range s1 {
		cnt1[i%2][c-'a']++
		cnt2[i%2][s2[i]-'a']++
	}
	return cnt1 == cnt2
}

复杂度分析

• 时间复杂度：\mathcal{O}(n+|\Sigma|)，其中 n 为 s_1 的长度。
• 空间复杂度：\mathcal{O}(|\Sigma|)，其中 |\Sigma| 为字符集合的大小，本题中字符均为小写字母，所以 |\Sigma|=26。

思考题

改成 j-i=3 要怎么做？