最小交换以使字符串等于Leetcode解决方案


难度级别 中等
经常问 亚马逊
贪婪

问题陈述

给你两个 字符串 长度相等的s1和s2仅由字母“ x”和“ y”组成。 您可以交换属于不同字符串的任意两个字符,
您的任务是使两个字符串相等。 返回使两个字符串相等的最小交换次数;如果不可能使两个字符串相等,则返回-1。

使用案列

#1

s1 = "xx", s2 = "yy"
1

#2

s1 = "xy", s2 = "yx"
2

方式(贪婪)

如果我们在第ith个索引处查看两个字符串中的字符,我们会发现只有4个可能的对{s1 [i],s2 [i]}:{“ x”,“ x”},{“ y ,“ y”},{“ x”,“ y”},{“ y”,“ x”}。
对于前两种类型的对s1 [i]等于s2 [i](这就是我们想要的),在这种情况下所需的交换次数将为零。

对于其余的对,我们的s1 [i]不等于s2 [i],因此我们需要使用交换操作。

我们可以通过两种方式使用它:

(i)如果我们在索引i和j处都有第三(或第四)类型对(i不等于j),如果我们将s3 [i]与s4 [j]交换,则s1 [i]将等于s2 [i](即s [i] = s1 [i])
且s1 [j]等于s2 [j](即s1 [j] = s2 [j]),这意味着可以使s1 [i] = s2 [i]和s1 [j] = s2 [ j]。

最小交换以使字符串等于Leetcode解决方案

 

(ii)如果我们在索引i处有第三对配对,而在某个索引j处有第四对配对(反之亦然):{“ x”,“ y”},{“ y”,“ x”}。 因此,使s3 [i] = s4 [i]和
s1 [j] = s2 [j]我们需要交换两次,首先我们需要将s1 [i]与s2 [i]交换,现在配对看起来像:{“ y”,“ x”},{“ y, “X”}。 现在我们需要将s1 [i]与s2 [j]交换,我们将得到
s1 [i] = s2 [i]和s1 [j] = s2 [j]。

 

最小交换以使字符串等于Leetcode解决方案

 

如我们所见,(i)类型操作只需要动一步就可以建立两个索引,因此我们将尽力进行(i)类型操作。 我们可以轻松地获得所有的计数
对的类型。 假设我们得到{“ x”,“ y”}对的数量= n1,得到{“ y”,“ x”}对的数量= n2。
我们可以一次交换2对类型3的货币对。 因此,我们需要结算n1对的总掉期将为n1 / 2,如果n1为奇数,那么一对将保持未结算状态。

对于n2同样。 如果n1和n2都为奇数,我们将得到一对未结算的货币对,因此我们可以使用(ii)类型的操作,该操作需要进行两次交换才能使它们稳定。
否则,如果n1和n2的奇偶校验不相同(即n1是奇数,n2是偶数),那么我们将得到一对尚未解决的对,
在这种情况下,将不可能使字符串相等。

实施

最小交换使字符串等于Leetcode解决方案的C ++程序

#include<bits/stdc++.h>
using namespace std;
int minimumSwap(string s1, string s2) 
{
    int xy_count=0,//count of {x,y} pairs
    yx_count=0,//count of {y,x} pairs
    n=s1.length();
    for(int i=0;i<n;i++)
    {
        if(s1[i]!=s2[i])
        {
            if(s1[i]=='x') xy_count++;
            else yx_count++;
        }
    }
    if(xy_count%2==yx_count%2) return (xy_count+yx_count)/2+(xy_count%2==1);//if parity of count of xy pair and yx pair is same 
    else return -1;
}

int main()
{
    string s1="xxxyy",s2="yyxxx";
    cout<<minimumSwap(s1,s2);
    return 0;
}
2

Java程序,用于最小交换以使字符串等于Leetcode解决方案

class Rextester{
    
      public static int minimumSwap(String s1, String s2) 
      {
         
        int xy_count=0,//count of {x,y} pairs
        yx_count=0,//count of {y,x} pairs
        n=s1.length();
        for(int i=0;i<n;i++)
        {
            if(s1.charAt(i)!=s2.charAt(i))
            {
                if(s1.charAt(i)=='x') xy_count++;
                else yx_count++;
            }
        }

        //if parity of count of xy pair and yx pair is same 
        if(xy_count%2==yx_count%2) return (xy_count+yx_count)/2+((xy_count%2==1)?1:0);
        else return -1;
    }
    
    public static void main(String args[])
    {
       	String s1="xxxyy",s2="yyxxx";
        System.out.println(minimumSwap(s1,s2) );
    }
}
2

最小交换以使字符串等于Leetcode解决方案的复杂度分析

时间复杂度

上) : 其中n是字符串的长度。 由于我们仅对两个字符串进行一次迭代,因此时间复杂度将为O(n)。

空间复杂度

O(1): 我们没有使用任何多余的空间。