Question

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

English Version

题目描述

给你两个字符串 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 只包含小写英文字母。

解法

方法一：计数

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

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

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

相似题目：

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

class Solution:
  def checkStrings(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 checkStrings(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 checkStrings(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 checkStrings(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 checkStrings(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;
}