Medium

题目描述

给你两个长度为 n 的字符串 s1 和 s2，都由小写英文字母组成。

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

  • 选择任意两个下标 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 <= 10^5
  • s1 和 s2 只包含小写英文字母

提示：

  • 两个位置的字符可以交换当且仅当这两个位置具有相同的奇偶性
  • 为了使两个字符串相等，字符串中偶数位置和奇数位置的字符应该是相同的

解题思路

解题思路

这道题的关键在于理解操作的限制：只能交换索引差为偶数的字符。这意味着：

  • 奇数位置的字符只能与奇数位置的字符交换
  • 偶数位置的字符只能与偶数位置的字符交换

换句话说，奇数位置和偶数位置的字符是相互独立的两个集合，它们不能互相交换。

因此，要使两个字符串相等，必须满足以下条件：

  1. s1 中所有奇数位置的字符集合必须与 s2 中所有奇数位置的字符集合相同
  2. s1 中所有偶数位置的字符集合必须与 s2 中所有偶数位置的字符集合相同

具体实现方法：

  1. 分别统计两个字符串在奇数位置和偶数位置的字符频次
  2. 比较对应位置的字符频次是否相同

这种方法的时间复杂度为 O(n)，空间复杂度为 O(1)（因为只有26个小写字母）。

另一种思路是将奇偶位置的字符分别提取出来排序后比较，但频次统计的方法更直观且效率相当。

代码实现

class Solution {
public:
    bool checkStrings(string s1, string s2) {
        vector<int> evenCount1(26, 0), evenCount2(26, 0);
        vector<int> oddCount1(26, 0), oddCount2(26, 0);
        
        for (int i = 0; i < s1.length(); i++) {
            if (i % 2 == 0) {
                evenCount1[s1[i] - 'a']++;
                evenCount2[s2[i] - 'a']++;
            } else {
                oddCount1[s1[i] - 'a']++;
                oddCount2[s2[i] - 'a']++;
            }
        }
        
        return evenCount1 == evenCount2 && oddCount1 == oddCount2;
    }
};

class Solution:
    def checkStrings(self, s1: str, s2: str) -> bool:
        even_count1 = [0] * 26
        even_count2 = [0] * 26
        odd_count1 = [0] * 26
        odd_count2 = [0] * 26
        
        for i in range(len(s1)):
            if i % 2 == 0:
                even_count1[ord(s1[i]) - ord('a')] += 1
                even_count2[ord(s2[i]) - ord('a')] += 1
            else:
                odd_count1[ord(s1[i]) - ord('a')] += 1
                odd_count2[ord(s2[i]) - ord('a')] += 1
        
        return even_count1 == even_count2 and odd_count1 == odd_count2

public class Solution {
    public bool CheckStrings(string s1, string s2) {
        int[] evenCount1 = new int[26];
        int[] evenCount2 = new int[26];
        int[] oddCount1 = new int[26];
        int[] oddCount2 = new int[26];
        
        for (int i = 0; i < s1.Length; i++) {
            if (i % 2 == 0) {
                evenCount1[s1[i] - 'a']++;
                evenCount2[s2[i] - 'a']++;
            } else {
                oddCount1[s1[i] - 'a']++;
                oddCount2[s2[i] - 'a']++;
            }
        }
        
        return ArrayEquals(evenCount1, evenCount2) && ArrayEquals(oddCount1, oddCount2);
    }
    
    private bool ArrayEquals(int[] arr1, int[] arr2) {
        for (int i = 0; i < arr1.Length; i++) {
            if (arr1[i] != arr2[i]) return false;
        }
        return true;
    }
}

var checkStrings = function(s1, s2) {
    if (s1.length !== s2.length) return false;
    
    const evenChars1 = [];
    const oddChars1 = [];
    const evenChars2 = [];
    const oddChars2 = [];
    
    for (let i = 0; i < s1.length; i++) {
        if (i % 2 === 0) {
            evenChars1.push(s1[i]);
            evenChars2.push(s2[i]);
        } else {
            oddChars1.push(s1[i]);
            oddChars2.push(s2[i]);
        }
    }
    
    evenChars1.sort();
    evenChars2.sort();
    oddChars1.sort();
    oddChars2.sort();
    
    return evenChars1.join('') === evenChars2.join('') && 
           oddChars1.join('') === oddChars2.join('');
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n)需要遍历一次字符串，n为字符串长度
空间复杂度O(1)使用固定大小的数组存储26个字母的频次