最小交換以使字符串等於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): 我們沒有使用任何多餘的空間。