Retournements de sous-chaînes minimum requis pour convertir une chaîne binaire en une autre

Afficher la discussion

Améliorer l’article

Enregistrer l’article

J’aime l’article

Afficher la discussion

Améliorer l’article

Enregistrer l’article

J’aime l’article

Étant donné deux chaînes binaires S1 et S2 de taille N et M respectivement, la tâche est de trouver le nombre minimum d’inversion de sous-chaînes de caractères égaux requis pour convertir la chaîne S1 à S2. S’il n’est pas possible de convertir la chaîne S1 à S2puis imprimez “-1”.

Exemples:

Saisir: S1 = “100001”, S2 = “110111”
Production: 2
Explication:
Initialement chaîne S1 = “100001”.
Renversement 1 : Inverser la sous-chaîne S1[1, 1]alors la chaîne S1 devient « 110001 ».
Renversement 2 : Inverser la sous-chaîne S1[3, 4]alors la chaîne S1 devient « 110111 ».
Après les inversions ci-dessus, les chaînes S1 et S2 sont égales.
Par conséquent, le nombre d’inversions est de 2.

Saisir: S1 = 101, S2 = 10
Production: -1

Approcher: Suivez les étapes ci-dessous pour résoudre ce problème :

  • Initialiser une variable, disons réponsepour stocker le nombre résultant d’inversions requises.
  • Si la longueur des chaînes données S1 et S2 ne sont pas les mêmes, puis imprimez “-1”.
  • Itérer sur la plage [0, N – 1] et effectuez les étapes suivantes :
    • Si S1[i] et S2[i] ne sont pas les mêmes, puis itérer jusqu’à S1[i] et S2[i] sont identiques. Incrémenter la réponse de 1 car la sous-chaîne actuelle doit être inversée.
    • Autrement, Continuez à la prochaine itération.
  • Après avoir terminé les étapes ci-dessus, imprimez la valeur du réponse comme le retournement résultant des sous-chaînes requis.

Voici la mise en œuvre de l’approche ci-dessus :

C++

#include <bits/stdc++.h>

using namespace std;

int canMakeSame(string s1, string s2)

{

    

    

    int ans = 0;

    

    

    if (s1.size() != s2.size()) {

        return -1;

    }

    int N = s1.length();

    

    for (int i = 0; i < N; i++) {

        

        

        if (s1[i] != s2[i]) {

            

            while (i < s1.length()

                   && s1[i] != s2[i]) {

                i++;

            }

            

            ans++;

        }

    }

    

    

    return ans;

}

int main()

{

    string S1 = "100001";

    string S2 = "110111";

    

    cout << canMakeSame(S1, S2);

    return 0;

}

Java

import java.io.*;

class GFG

{

  

  

  

  static int canMakeSame(String s1, String s2)

  {

    

    

    int ans = 0;

    

    

    if (s1.length() != s2.length()) {

      return -1;

    }

    int N = s1.length();

    

    for (int i = 0; i < N; i++)

    {

      

      

      if (s1.charAt(i) != s2.charAt(i))

      {

        

        while (i < s1.length()

               && s1.charAt(i) != s2.charAt(i))

        {

          i++;

        }

        

        ans++;

      }

    }

    

    

    return ans;

  }

  

  public static void main(String[] args)

  {

    String S1 = "100001";

    String S2 = "110111";

    

    System.out.println(canMakeSame(S1, S2));

  }

}

Python3

def canMakeSame(s1, s2) :

    

    

    

    ans = -1

    

    

    if (len(s1) != len(s2)) :

        return -1

    N = len(s1)

    

    for i in range(0, N):

        

        

        if (s1[i] != s2[i]) :

            

            while (i < len(s1)

                and s1[i] != s2[i]) :

                i += 1

            

            

            ans += 1

    

    

    

    return ans

S1 = "100001"

S2 = "110111"

print(canMakeSame(S1, S2))

C#

using System;

class GFG{

  

  

  

  static int canMakeSame(string s1, string s2)

  {

    

    

    int ans = 0;

    

    

    if (s1.Length != s2.Length) {

      return -1;

    }

    int N = s1.Length;

    

    for (int i = 0; i < N; i++)

    {

      

      

      if (s1[i] != s2[i])

      {

        

        while (i < s1.Length

               && s1[i] != s2[i])

        {

          i++;

        }

        

        ans++;

      }

    }

    

    

    return ans;

  }

public static void Main(string[] args)

{

    string S1 = "100001";

    string S2 = "110111";

    

    Console.Write(canMakeSame(S1, S2));

}

}

Javascript

<script>

function canMakeSame(s1, s2)

{

    

    

    var ans = 0;

    

    

    if (s1.length != s2.length) {

        return -1;

    }

    var N = s1.length;

    

    for (var i = 0; i < N; i++) {

        

        

        if (s1[i] != s2[i]) {

            

            while (i < s1.length

                   && s1[i] != s2[i]) {

                i++;

            }

            

            ans++;

        }

    }

    

    

    return ans;

}

var S1 = "100001";

var S2 = "110111";

document.write( canMakeSame(S1, S2));

</script>

Complexité temporelle : SUR)
Espace Auxiliaire : O(1)

Laisser un commentaire

Votre adresse e-mail ne sera pas publiée. Les champs obligatoires sont indiqués avec *