Nombre minimum d’étapes nécessaires pour supprimer la sous-chaîne K d’une chaîne donnée

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

Soit une chaîne binaire Set une sous-chaîne Kla tâche consiste à trouver le nombre minimum d’étapes requises pour retourner les caractères dans une chaîne binaire de sorte qu’elle ne contienne pas la sous-chaîne donnée K. Noter: En une seule étape, nous pouvons changer 0 en 1 ou vice versa.
Exemples:

Saisir: S = “0111011”, K = “011”
Production: 2
Explication:
Dans la chaîne ci-dessus, nous avons la sous-chaîne 011 pour 2 fois, donc changez le 3ème bit et le 7ème bit.

Saisir: S = “010010”, K = “0100”
Production: 1
Explication:
Dans la chaîne ci-dessus, nous avons la sous-chaîne 0100 pour 1 fois, changez le 4ème bit de la chaîne en 1.

Approche naïve : L’approche naïve consiste à utiliser le Recherche de motif. Itérer dans la chaîne pour N ! fois(N = longueur de la chaîne binaire). À chaque itération, vérifiez la sous-chaîne K et si c’est une correspondance, incrémentez le compte. Enfin, imprimez le nombre qui sera le nombre d’étapes nécessaires pour rendre la chaîne telle qu’elle ne contienne pas la sous-chaîne donnée K.

Complexité temporelle : O(M*N)M est la longueur de la sous-chaîne et N est la longueur de la chaîne binaire.
Espace Auxiliaire : O(1)

Approche efficace : Pour optimiser la méthode ci-dessus, l’idée est de remplacer la sous-chaîne par une chaîne vide et soustrayez la longueur de chaîne résultante de la longueur de chaîne d’origine. Après cela, divisez la chaîne résultante avec la longueur de la sous-chaîne donnée K pour obtenir le nombre minimum d’étapes requises pour retourner les caractères de la chaîne donnée S afin qu’il ne contienne pas la sous-chaîne donnée K.

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

C++

#include<bits/stdc++.h>

#include <boost/algorithm/string/replace.hpp>

using namespace std;

int flipCharacters(string b,

                   string sub)

{

    

    

    

    

    

    

    int res = b.size();

    boost::replace_all(b, sub, "");

    res = res - b.size();

             

    

    

    int temp = res / sub.size();

    

    return temp;

}

int main()

{

    

    

    string S = "010010";

    string K = "0100";

    

    int result = flipCharacters(S, K);

    

    cout << (result);

}

Java

import java.util.*;

public class Test {

    

    

    

    

    static int flipCharacters(String b,

                              String sub)

    {

        

        

        

        

        

        int res = b.length()

                  - b.replaceAll(sub, "")

                        .length();

        

        

        int temp = res / sub.length();

        

        return temp;

    }

    

    public static void main(String[] args)

    {

        

        String S = "010010";

        String K = "0100";

        

        int result = flipCharacters(S, K);

        

        System.out.println(result);

    }

}

Python3

def flipCharacters(b, sub):

    

    

    

    b1 = b.replace(sub, "")

    

    n = int((len(b)-len(b1))/len(sub))

    

    return n

if __name__ == '__main__':

    S ="010010"

    X ="0100"

    result = flipCharacters(S, X)

    print(result)

C#

using System;

class GFG

{

 

  

  

  

  

  static int flipCharacters(string b,

                            string sub)

  {

    

    

    

    

    

    int res = b.Length -

              b.Replace(sub, "").Length;

    

    

    int temp = res / sub.Length;

    

    return temp;

  }

  

  public static void Main(string[] args)

  {

    

    string S = "010010";

    string K = "0100";

    

    int result = flipCharacters(S, K);

    

    Console.Write(result);

  }

}

Javascript

<script>

function flipCharacters(b, sub)

{

    

    

    

    

    

    

    var res = b.length - b.replace(sub, "").length;

             

    

    

    var temp = parseInt(res / sub.length);

    

    return temp;

}

var S = "010010";

var K = "0100";

var result = flipCharacters(S, K);

document.write(result);

</script>

Complexité temporelle : SUR)où N est la longueur de la chaîne.
Espace Auxiliaire : O(1)

Laisser un commentaire

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