Easy

题目描述

给你两个字符串 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 仅由小写英文字母组成

解题思路

这道题的关键在于理解交换规则：只能交换距离为 2 的字符，即只能交换 (0,2) 和 (1,3) 位置的字符。

解法分析：

由于字符串长度固定为 4，且只能进行两种交换操作：

  1. 交换位置 0 和位置 2 的字符
  2. 交换位置 1 和位置 3 的字符

观察规律：

  • 位置 0 和位置 2 可以互相交换，它们形成一个独立的组
  • 位置 1 和位置 3 可以互相交换，它们形成另一个独立的组
  • 两个组之间无法交换字符

解题思路：

  1. 分组比较法：将字符串按奇偶位置分组，比较两个字符串的对应组是否包含相同字符
  2. 暴力枚举法：由于只有 2^2 = 4 种可能的状态，可以枚举所有可能的交换组合

推荐使用分组比较法，因为它更直观且时间复杂度更优。具体做法是：

  • 将 s1 和 s2 的偶数位置字符分别排序后比较
  • 将 s1 和 s2 的奇数位置字符分别排序后比较
  • 只有当两组都相等时，才能通过操作使字符串相等

代码实现

class Solution {
public:
    bool canBeEqual(string s1, string s2) {
        // 分别比较偶数位置和奇数位置的字符
        string even1 = "", odd1 = "", even2 = "", odd2 = "";
        
        for (int i = 0; i < 4; i++) {
            if (i % 2 == 0) {
                even1 += s1[i];
                even2 += s2[i];
            } else {
                odd1 += s1[i];
                odd2 += s2[i];
            }
        }
        
        sort(even1.begin(), even1.end());
        sort(even2.begin(), even2.end());
        sort(odd1.begin(), odd1.end());
        sort(odd2.begin(), odd2.end());
        
        return even1 == even2 && odd1 == odd2;
    }
};

class Solution:
    def canBeEqual(self, s1: str, s2: str) -> bool:
        # 分别获取偶数位置和奇数位置的字符
        even1 = [s1[i] for i in range(0, 4, 2)]
        odd1 = [s1[i] for i in range(1, 4, 2)]
        even2 = [s2[i] for i in range(0, 4, 2)]
        odd2 = [s2[i] for i in range(1, 4, 2)]
        
        # 排序后比较
        return sorted(even1) == sorted(even2) and sorted(odd1) == sorted(odd2)

public class Solution {
    public bool CanBeEqual(string s1, string s2) {
        // 分别获取偶数位置和奇数位置的字符
        var even1 = new List<char>();
        var odd1 = new List<char>();
        var even2 = new List<char>();
        var odd2 = new List<char>();
        
        for (int i = 0; i < 4; i++) {
            if (i % 2 == 0) {
                even1.Add(s1[i]);
                even2.Add(s2[i]);
            } else {
                odd1.Add(s1[i]);
                odd2.Add(s2[i]);
            }
        }
        
        even1.Sort();
        even2.Sort();
        odd1.Sort();
        odd2.Sort();
        
        return even1.SequenceEqual(even2) && odd1.SequenceEqual(odd2);
    }
}

/**
 * @param {string} s1
 * @param {string} s2
 * @return {boolean}
 */
var canBeEqual = function(s1, s2) {
    const evenS1 = [s1[0], s1[2]].sort();
    const oddS1 = [s1[1], s1[3]].sort();
    const evenS2 = [s2[0], s2[2]].sort();
    const oddS2 = [s2[1], s2[3]].sort();
    
    return evenS1[0] === evenS2[0] && evenS1[1] === evenS2[1] && 
           oddS1[0] === oddS2[0] && oddS1[1] === oddS2[1];
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型值说明
时间复杂度O(1)字符串长度固定为4，排序操作为常数时间
空间复杂度O(1)只使用常数级别的额外空间