leetcode
leetcode 1151 ~ 1200
交换字符使得字符串相同

交换字符使得字符串相同

难度:

标签:

题目描述

代码结果

运行时间: 23 ms, 内存: 16.0 MB


/*
 * Problem: We have two strings s1 and s2 of the same length, containing only the characters 'x' and 'y'. We want to make them identical by swapping characters between the two strings. The goal is to find the minimum number of swaps needed, or return -1 if it is not possible.
 *
 * Approach using Java Streams:
 * 1. Use IntStream to iterate over the strings and count the number of 'xy' and 'yx' mismatches.
 * 2. Apply the same logic as the regular Java approach to determine the number of swaps.
 */

import java.util.stream.IntStream;

public int minimumSwapStream(String s1, String s2) {
    long xy_count = IntStream.range(0, s1.length())
                            .filter(i -> s1.charAt(i) == 'x' && s2.charAt(i) == 'y')
                            .count();
    long yx_count = IntStream.range(0, s1.length())
                            .filter(i -> s1.charAt(i) == 'y' && s2.charAt(i) == 'x')
                            .count();

    if ((xy_count + yx_count) % 2 != 0) {
        return -1;
    }

    return (int)(xy_count / 2 + yx_count / 2 + (xy_count % 2) * 2);
}

解释

方法:

此题解首先通过遍历字符串 s1 和 s2,统计两种不匹配情况的个数:s1中的'x'与s2中的'y'的不匹配个数(xy),以及s1中的'y'与s2中的'x'的不匹配个数(yx)。接着,检查这两个计数(xy 和 yx)之和是否为奇数,如果是奇数,则无法通过交换使两字符串相同,因此返回-1。如果是偶数,则计算将这些不匹配通过最少交换次数解决所需要的交换次数。每两个 xy 或 yx 可以通过一次交换解决(即 xy//2 + yx//2 次),而每有一个单独的 xy 或 yx 将需要额外两次交换(这是因为单独的一个 xy 和一个 yx 可以组合成一次交换)。因此,总的交换次数为 xy//2 + yx//2 + xy%2 + yx%2。

时间复杂度:

O(n)

空间复杂度:

O(1)

代码细节讲解

🦆
为什么当不匹配的总数(xy + yx)为奇数时,就无法通过交换使两个字符串相同?
每次交换都涉及两个不匹配的字符,一个是xy类型,另一个是yx类型。如果不匹配的总数是奇数,这意味着至少有一个xy或yx无法找到对应的配对进行交换。因为每次有效的交换都必须处理一对不匹配(一个xy和一个yx),奇数个不匹配意味着至少有一个无法被配对,从而无法通过交换来完全匹配两个字符串。
🦆
题解中提到了'每两个xy或yx可以通过一次交换解决',请问是如何通过一次交换解决两个不匹配的?具体的交换过程是怎样的?
这里的表述有误,正确的解释应该是:每两个相同类型的不匹配(要么是两个xy,要么是两个yx)可以通过一次交换解决。例如,如果有两个xy不匹配,即s1中的位置i和j都是'x'而s2中相应位置都是'y',那么可以通过交换s2中的这两个位置的'y'来解决这两个不匹配。同理,对于两个yx不匹配也是相同的处理方式。
🦆
题解提到对于单独的一个xy和一个yx可以组合成一次交换,那么如果有多余的单个xy或yx,而另一个不足以配对,这种情况应该如何处理?
当有单独的xy和yx时,可以通过一次交换来解决这两个不匹配(交换一个xy位置的x与一个yx位置的y)。然而,如果有多余的单个xy或yx而另一个不足以配对,这种情况无法通过正常交换解决,因为每个有效的交换需要一个xy和一个yx。这样的情况会导致无法使两个字符串通过交换完全相同,这也是为什么检查(xy + yx)是否为奇数很重要的原因。
🦆
题解中的算法对于所有情况的处理是否已经足够全面,还是存在某些特殊情况没有考虑到?
题解中的算法已经足够全面地处理了此问题的所有普通情况。它考虑了所有不匹配的可能性,并正确地计算了进行有效交换的最小次数。它还考虑了当不匹配的总数为奇数时,无法完成交换的情况。因此,算法已经涵盖了所有必要的逻辑来解决这个问题。

相关问题