leetcode
leetcode 2401 ~ 2450
判断通过操作能否让字符串相等 II

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

难度:

标签:

题目描述

You are given two strings s1 and s2, both of length n, consisting of lowercase English letters.

You can apply the following operation on any of the two strings any number of times:

  • Choose any two indices i and j such that i < j and the difference j - i is even, then swap the two characters at those indices in the string.

Return true if you can make the strings s1 and s2 equal, and false otherwise.

 

Example 1:

Input: s1 = "abcdba", s2 = "cabdab"
Output: true
Explanation: We can apply the following operations on s1:
- Choose the indices i = 0, j = 2. The resulting string is s1 = "cbadba".
- Choose the indices i = 2, j = 4. The resulting string is s1 = "cbbdaa".
- Choose the indices i = 1, j = 5. The resulting string is s1 = "cabdab" = s2.

Example 2:

Input: s1 = "abe", s2 = "bea"
Output: false
Explanation: It is not possible to make the two strings equal.

 

Constraints:

  • n == s1.length == s2.length
  • 1 <= n <= 105
  • s1 and s2 consist only of lowercase English letters.

代码结果

运行时间: 75 ms, 内存: 16.5 MB

/*
 * 思路：
 * 使用 Java Stream API 实现与上述相同的逻辑。
 * 分别处理偶数下标和奇数下标的字符，并比较它们排序后的结果。
 */

import java.util.Arrays;
import java.util.stream.Collectors;

public class Solution {
    public boolean canBeEqual(String s1, String s2) {
        if (s1.length() != s2.length()) return false;

        String s1Even = Arrays.stream(s1.split(""))
                                .filter((s, i) -> i % 2 == 0)
                                .sorted()
                                .collect(Collectors.joining());

        String s1Odd = Arrays.stream(s1.split(""))
                               .filter((s, i) -> i % 2 != 0)
                               .sorted()
                               .collect(Collectors.joining());

        String s2Even = Arrays.stream(s2.split(""))
                                .filter((s, i) -> i % 2 == 0)
                                .sorted()
                                .collect(Collectors.joining());

        String s2Odd = Arrays.stream(s2.split(""))
                               .filter((s, i) -> i % 2 != 0)
                               .sorted()
                               .collect(Collectors.joining());

        return s1Even.equals(s2Even) && s1Odd.equals(s2Odd);
    }
}

解释

方法:

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

时间复杂度:

O(n)

空间复杂度:

O(1)

代码细节讲解

🦆
为什么在这个问题中，只考虑偶数索引和奇数索引的字符集合是否相同就足以判断两个字符串是否可以通过特定交换操作变得相同？
▷
根据题目的操作规则，字符的交换只能在索引间隔为偶数的情况下进行。这意味着任何位于偶数索引的字符只能与其他偶数索引的字符交换位置，同理，奇数索引的字符也只能与其他奇数索引的字符交换。因此，为了使两个字符串通过交换变得相同，字符串s1的偶数索引位置上的字符集合必须与字符串s2的偶数索引位置上的字符集合相同，奇数索引位置也是如此。只有这样，每个字符才可能通过交换找到对应的位置，从而让两个字符串完全相同。
🦆
在使用Counter来比较两个字符串的字符频次时，是否考虑了字符的具体位置，还是仅仅比较了偶数和奇数位置上字符的总体频次？
▷
在使用Counter进行比较时，并没有考虑字符在字符串中的具体位置，而是仅仅统计了字符在偶数和奇数位置上的总体频次。这是因为题目的操作规则允许在同奇偶性的索引间自由交换字符，因此只需要确保相同奇偶性索引的字符频次相同即可，而具体每个字符位于哪一个具体的偶数或奇数位置则不影响最终能否通过交换使两个字符串相同。
🦆
假设输入的字符串中包含重复的字符，这种情况下Counter的比较是否仍然有效？
▷
是的，Counter的比较在输入字符串中包含重复字符的情况下仍然有效。Counter会计算每个字符在字符串中出现的次数，不管这些字符是否重复出现。通过比较两个字符串中相同索引奇偶性位置上的字符频次，可以确保即使字符重复，只要频次相同，就能通过合法的交换操作使两个字符串相等。
🦆
题解中是否考虑了如果字符串长度非常大时，对内存和性能的影响？
▷
题解中使用了Counter来统计字符频次，这种方法在处理大字符串时可能会对内存和性能产生一定的影响。计数操作需要存储每个字符及其出现的次数，如果字符集很大或字符串很长，这将需要相应更多的内存。此外，对字符串进行切片操作以分离偶数和奇数索引的字符也会消耗额外的时间和空间。尽管如此，这种方法在许多实际情况下仍然是有效和可行的，尤其是在字符种类有限的情况下。

相关问题

判别首字母缩略词销售利润最大化