2839. 判断通过操作能否让字符串相等 I

题目描述

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

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

选择两个下标 i 和 j 且满足 j - i = 2 ，然后交换这个字符串中两个下标对应的字符。

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

示例 1：

输入：s1 = "abcd", s2 = "cdab"
输出：true
解释： 我们可以对 s1 执行以下操作：
- 选择下标 i = 0 ，j = 2 ，得到字符串 s1 = "cbad" 。
- 选择下标 i = 1 ，j = 3 ，得到字符串 s1 = "cdab" = s2 。

示例 2：

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

提示：

s1.length == s2.length == 4
s1 和 s2 只包含小写英文字母。

解法

方法一：计数

我们观察题目中的操作，可以发现，如果字符串的两个下标 $i$ 和 $j$ 的奇偶性相同，那么它们可以通过交换改变顺序。

因此，我们可以统计两个字符串中奇数下标的字符的出现次数，以及偶数下标的字符的出现次数，如果两个字符串的统计结果相同，那么我们就可以通过操作使得两个字符串相等。

时间复杂度 $O(n + |\Sigma|)$，空间复杂度 $O(|\Sigma|)$。其中 $n$ 是字符串的长度，而 $\Sigma$ 是字符集。

相似题目：

2840. 判断通过操作能否让字符串相等 II

Python3JavaC++GoTypeScript

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

class Solution {
    public boolean canBeEqual(String s1, String s2) {
        int[][] cnt = new int[2][26];
        for (int i = 0; i < s1.length(); ++i) {
            ++cnt[i & 1][s1.charAt(i) - 'a'];
            --cnt[i & 1][s2.charAt(i) - 'a'];
        }
        for (int i = 0; i < 26; ++i) {
            if (cnt[0][i] != 0 || cnt[1][i] != 0) {
                return false;
            }
        }
        return true;
    }
}

class Solution {
public:
    bool canBeEqual(string s1, string s2) {
        vector<vector<int>> cnt(2, vector<int>(26, 0));
        for (int i = 0; i < s1.size(); ++i) {
            ++cnt[i & 1][s1[i] - 'a'];
            --cnt[i & 1][s2[i] - 'a'];
        }
        for (int i = 0; i < 26; ++i) {
            if (cnt[0][i] || cnt[1][i]) {
                return false;
            }
        }
        return true;
    }
};

func canBeEqual(s1 string, s2 string) bool {
    cnt := [2][26]int{}
    for i := 0; i < len(s1); i++ {
        cnt[i&1][s1[i]-'a']++
        cnt[i&1][s2[i]-'a']--
    }
    for i := 0; i < 26; i++ {
        if cnt[0][i] != 0 || cnt[1][i] != 0 {
            return false
        }
    }
    return true
}

function canBeEqual(s1: string, s2: string): boolean {
    const cnt: number[][] = Array.from({ length: 2 }, () => Array.from({ length: 26 }, () => 0));
    for (let i = 0; i < s1.length; ++i) {
        ++cnt[i & 1][s1.charCodeAt(i) - 97];
        --cnt[i & 1][s2.charCodeAt(i) - 97];
    }
    for (let i = 0; i < 26; ++i) {
        if (cnt[0][i] || cnt[1][i]) {
            return false;
        }
    }
    return true;
}

2839. 判断通过操作能否让字符串相等 I

题目描述

解法

方法一：计数

评论