Solutions CS101

Appearance

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

string, sorting, https://leetcode.cn/problems/check-if-strings-can-be-made-equal-with-operations-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 <= 10^5
  • s1 和 s2 只包含小写英文字母。

这道题的核心在于理解题目给出的交换条件：只能交换下标差值为偶数（j−i 是偶数）的两个字符。

核心思路

  1. 下标奇偶性不变： 如果两个下标 i 和 j 的差值是偶数，那么 i 和 j 的奇偶性必然相同（同为偶数或同为奇数）。 这意味着：

    • 下标为偶数的字符只能与下标为偶数的字符交换。
    • 下标为奇数的字符只能与下标为奇数的字符交换。

  2. 任意交换性： 由于可以执行任意次数的操作，在同一组（偶数下标组或奇数下标组）内的字符可以被排列成任意顺序。这类似于在一个子数组内进行冒泡排序。

  3. 等价条件： 字符串 s1 能够转化为 s2 的充要条件是：

    • s1 中所有偶数下标位置出现的字符及其频次，与 s2 中所有偶数下标位置出现的字符及其频次完全一致。
    • s1 中所有奇数下标位置出现的字符及其频次，与 s2 中所有奇数下标位置出现的字符及其频次完全一致。

    算法步骤

  4. 提取 s1 和 s2 的偶数下标字符序列，判断它们排序后是否相等（或者统计字符频率是否相等）。

  5. 提取 s1 和 s2 的奇数下标字符序列，判断它们排序后是否相等。

  6. 如果两个条件都满足，返回 true，否则返回 false。

Python 代码实现

python
class Solution:
    def checkStrings(self, s1: str, s2: str) -> bool:
        # s1[0::2] 表示从索引 0 开始，步长为 2 的切片（即偶数下标：0, 2, 4...）
        # s1[1::2] 表示从索引 1 开始，步长为 2 的切片（即奇数下标：1, 3, 5...）
        
        # 检查偶数下标位置的字符集合是否相同
        even_match = sorted(s1[0::2]) == sorted(s2[0::2])
        
        # 检查奇数下标位置的字符集合是否相同
        odd_match = sorted(s1[1::2]) == sorted(s2[1::2])
        
        return even_match and odd_match

复杂度分析

  • 时间复杂度：O(nlog⁡n)。
    • 切片操作耗时 O(n)。
    • 排序操作耗时 O(nlog⁡n)，其中 n 为字符串长度。
    • 在字符集很小（仅小写字母）的情况下，也可以使用哈希表（Counter）统计频率，将复杂度优化到 O(n)。
  • 空间复杂度：O(n)。
    • 存储切片后的子字符串需要额外的空间。