Ελάχιστες ανταλλαγές για να κάνουν τις συμβολοσειρές ίσες με τη λύση 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) εάν έχουμε ζεύγος τύπου 3ου (ή 4ου) και στα δύο ευρετήρια i και j (i δεν είναι ίσο με j), εάν αλλάξουμε το s1 [i] με το s2 [j] τότε το s1 [i] θα γίνει ίσο με το s2 [i] (δηλ. s [i] = s2 [i])
και το s1 [j] θα γίνει ίσο με το s2 [j] (δηλ. s1 [j] = s2 [j]), αυτό σημαίνει ότι σε μία κίνηση μπορεί να κάνει s1 [i] = s2 [i] και s1 [j] = s2 [ ι].

Ελάχιστες ανταλλαγές για να κάνουν τις συμβολοσειρές ίσες με τη λύση Leetcode

 

(ii) εάν έχουμε τον 3ο τύπο ζεύγους στο ευρετήριο i και τον 4ο τύπο ζεύγους σε κάποιο δείκτη j (ή αντίστροφα): {"x", "y"}, {"y", "x"}. έτσι, για να κάνετε s1 [i] = s2 [i] και
s1 [j] = s2 [j] πρέπει να ανταλλάξουμε δύο φορές, πρώτα πρέπει να ανταλλάξουμε s1 [i] με s2 [i], τώρα τα ζεύγη θα μοιάζουν: {"y", "x"}, {"y, "Χ"}. τώρα πρέπει να ανταλλάξουμε το s1 [i] με το s2 [j] και θα πάρουμε
s1 [i] = s2 [i] και s1 [j] = s2 [j].

 

Ελάχιστες ανταλλαγές για να κάνουν τις συμβολοσειρές ίσες με τη λύση Leetcode

 

όπως μπορούμε να δούμε ότι η λειτουργία τύπου (i) διαρκεί μόνο 1 κίνηση για να διευθετηθούν δύο ευρετήρια, οπότε θα προσπαθήσουμε να κάνουμε (i) λειτουργίες τύπου όσο μπορούμε. μπορούμε εύκολα να μετρήσουμε όλα
τύποι ζευγαριών. Ας υποθέσουμε ότι λαμβάνουμε τον αριθμό των {"x", "y"} ζευγών = n1, τον αριθμό των "" y "," x "} ζευγών = n2.
μπορούμε να τακτοποιήσουμε 2 ζευγάρια του τύπου 3 σε μία ανταλλαγή. οπότε η συνολική ανταλλαγή που πρέπει να διευθετήσουμε τα ζεύγη n1 θα είναι n1 / 2, εάν το n1 είναι μονό, ένα ζευγάρι θα παραμείνει ασταθές.

Ομοίως για το n2. εάν τα n1 και n2 είναι περίεργα, θα πάρουμε ένα ζεύγος καθένα απροστάτευτο, ώστε να μπορούμε να χρησιμοποιήσουμε (ii) λειτουργία τύπου που απαιτεί 2 ανταλλαγές για να τα διευθετήσουμε.
Διαφορετικά, εάν η ισοτιμία των n1 και n2 δεν είναι η ίδια (δηλ. το n1 είναι μονό και το n2 είναι ομοιόμορφο) τότε θα λάβουμε ένα ζευγάρι που δεν έχει διευθετηθεί,
Σε αυτήν την περίπτωση, θα είναι αδύνατο να κάνετε τις χορδές ίσες.

Εκτέλεση

Πρόγραμμα C ++ για Ελάχιστες ανταλλαγές για να κάνουν τις συμβολοσειρές ίσες με τη λύση Leetcode

#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): Δεν χρησιμοποιούμε επιπλέον χώρο.