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

标签: 哈希表 字符串 排序

难度: Medium

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

Submission

运行时间: 75 ms

内存: 16.5 MB

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

Explain

此题解采用的方法是通过计数比较。给定的操作允许我们交换字符串中索引i和j的字符，条件是j-i为偶数。这意味着可以在偶数索引位置自由交换字符，同样也可以在奇数索引位置自由交换。因此，只需要检查s1与s2在所有偶数位置的字符集合是否相同，以及所有奇数位置的字符集合是否相同。题解使用Counter类从collections模块来计数各个字符在偶数和奇数位置上的出现频次，只有当s1和s2在偶数位置和奇数位置的字符计数完全相同时，才能通过上述操作使s1变为s2。

时间复杂度: O(n)

空间复杂度: O(1)

class Solution:
    def checkStrings(self, s1: str, s2: str) -> bool:
        # 使用Counter统计字符串s1和s2在偶数索引的字符频次
        even_chars_match = Counter(s1[::2]) == Counter(s2[::2])
        # 使用Counter统计字符串s1和s2在奇数索引的字符频次
        odd_chars_match = Counter(s1[1::2]) == Counter(s2[1::2])
        # 如果偶数索引和奇数索引位置的字符频次都匹配，则返回True
        return even_chars_match and odd_chars_match

Explore

根据题目的操作规则，字符的交换只能在索引间隔为偶数的情况下进行。这意味着任何位于偶数索引的字符只能与其他偶数索引的字符交换位置，同理，奇数索引的字符也只能与其他奇数索引的字符交换。因此，为了使两个字符串通过交换变得相同，字符串s1的偶数索引位置上的字符集合必须与字符串s2的偶数索引位置上的字符集合相同，奇数索引位置也是如此。只有这样，每个字符才可能通过交换找到对应的位置，从而让两个字符串完全相同。

在使用Counter进行比较时，并没有考虑字符在字符串中的具体位置，而是仅仅统计了字符在偶数和奇数位置上的总体频次。这是因为题目的操作规则允许在同奇偶性的索引间自由交换字符，因此只需要确保相同奇偶性索引的字符频次相同即可，而具体每个字符位于哪一个具体的偶数或奇数位置则不影响最终能否通过交换使两个字符串相同。

是的，Counter的比较在输入字符串中包含重复字符的情况下仍然有效。Counter会计算每个字符在字符串中出现的次数，不管这些字符是否重复出现。通过比较两个字符串中相同索引奇偶性位置上的字符频次，可以确保即使字符重复，只要频次相同，就能通过合法的交换操作使两个字符串相等。

题解中使用了Counter来统计字符频次，这种方法在处理大字符串时可能会对内存和性能产生一定的影响。计数操作需要存储每个字符及其出现的次数，如果字符集很大或字符串很长，这将需要相应更多的内存。此外，对字符串进行切片操作以分离偶数和奇数索引的字符也会消耗额外的时间和空间。尽管如此，这种方法在许多实际情况下仍然是有效和可行的，尤其是在字符种类有限的情况下。