Vérifier si une chaîne peut être formée à partir d’une autre chaîne par au plus X décalages circulaires dans le sens des aiguilles d’une montre

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é un entier X et deux cordes S1 et S2la tâche consiste à vérifier cette chaîne S1 peut être converti en la chaîne S2 en décalant les caractères dans le sens des aiguilles d’une montre au moins X fois.

Saisir: S1 = “abcd”, S2 = “dddd”, X = 3
Production: Oui
Explication:
La chaîne donnée S1 peut être convertie en chaîne S2 comme-
Caractère “a” – Maj 3 fois – “d”
Caractère “b” – Shift 2 fois – “d”
Caractère “c” – Maj 1 fois – “d”
Caractère “d” – Maj 0 fois – “d”

Saisir: S1 = “vous”, S2 = “ara”, X = 6
Production: Oui
Explication:
La chaîne donnée S1 peut être convertie en chaîne S2 comme –
Caractère “y” – Décalage circulaire 2 fois – “a”
Caractère “o” – Maj 3 fois – “r”
Caractère “u” – Décalage circulaire 6 fois – “a”

Approcher: L’idée est de parcourir la chaîne et pour chaque index et de trouver la différence entre le Valeurs ASCII du caractère aux indices respectifs des deux chaînes. Si la différence est inférieure à 0, alors pour un décalage circulaire, ajoutez 26 pour obtenir la différence réelle. Si pour tout indice, la différence dépasse Xalors S2 ne peut pas être formé à partir S1sinon possible.
Voici la mise en œuvre de l’approche ci-dessus :

C++

#include <bits/stdc++.h>

using namespace std;

void isConversionPossible(string s1,

                          string s2, int x)

{

    int diff, n;

    n = s1.length();

    

    

    

    

    

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

        

        

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

            continue;

        

        

        

        diff = (int(s2[i] - s1[i])

                + 26)

               % 26;

        

        if (diff > x) {

            cout << "NO" << endl;

            return;

        }

    }

    cout << "YES" << endl;

}

int main()

{

    string s1 = "you";

    string s2 = "ara";

    int x = 6;

    

    isConversionPossible(s1, s2, x);

    return 0;

}

Java

import java.io.*;

import java.util.*;

class GFG{

    

static void isConversionPossible(String s1,

                                 String s2,

                                 int x)

{

    int diff = 0, n;

    n = s1.length();

    

    

    

    

    

    

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

    {

        

       

       

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

           continue;

       

       

       

       

       diff = ((int)(s2.charAt(i) -

                     s1.charAt(i)) + 26) % 26;

       

       

       if (diff > x)

       {

           System.out.println("NO");

           return;

       }

    }

    System.out.println("YES");

}

    

public static void main (String[] args)

{

    String s1 = "you";

    String s2 = "ara";

    int x = 6;

    

    isConversionPossible(s1, s2, x);

}

}

Python3

def isConversionPossible(s1, s2, x):

    n = len(s1)

    s1 = list(s1)

    s2 = list(s2)

    

    for i in range(n):

        

        

        

        diff = ord(s2[i]) - ord(s1[i])

        

        

        

        if diff == 0:

            continue

        

        

        

        

        

        if diff < 0:

            diff = diff + 26

        

        

        

        if diff > x:

            return False

    

    return True

    

if __name__ == "__main__":

    s1 = "you"

    s2 = "ara"

    x = 6

    

    

    result = isConversionPossible(s1, s2, x)

    

    if result:

        print("YES")

    else:

        print("NO")

C#

using System;

class GFG{

    

static void isConversionPossible(String s1,

                                 String s2,

                                 int x)

{

    int diff = 0, n;

    n = s1.Length;

    

    

    

    

    

    

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

    {

        

        

        

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

            continue;

            

        

        

        

        diff = ((int)(s2[i] -

                      s1[i]) + 26) % 26;

            

        

        if (diff > x)

        {

            Console.Write("NO");

            return;

        }

    }

    Console.Write("YES");

}

    

public static void Main ()

{

    String s1 = "you";

    String s2 = "ara";

    int x = 6;

    

    isConversionPossible(s1, s2, x);

}

}

Javascript

<script>

function isConversionPossible(s1,s2,x)

{

    let diff = 0, n;

    n = s1.length;

     

    

    

    

    

    

    for(let i = 0; i < n; i++)

    {

         

       

       

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

           continue;

        

       

       

       

       diff = ((s2[i].charCodeAt(0) -

                     s1[i].charCodeAt(0)) + 26) % 26;

        

       

       if (diff > x)

       {

           document.write("NO<br>");

           return;

       }

    }

    document.write("YES<br>");

}

let s1 = "you";

let s2 = "ara";

let x = 6;

isConversionPossible(s1, s2, x);

</script>

Complexité temporelle :O(N),N=Longueur(S1)

Espace Auxiliaire :O(1)

Laisser un commentaire

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