Vérifiez si la chaîne donnée est une sous-chaîne de chaîne formée par la concaténation répétée de z à un

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é une chaîne chaînela tâche consiste à vérifier si la chaîne chaîne est une sous-chaîne d’une chaîne de longueur infinie S dans lequel les alphabets minuscules sont concaténés dans l’ordre inverse comme suit :

S = “zyxwvutsrqponmlkjihgfedcbazyxwvutsrqponmlkjihgfedcba….”

Exemples:

Saisir: chaîne = “cbaz”
Production: OUI
Explication:
La chaîne donnée “cbaz” est une sous-chaîne valide de S.

Saisir: chaîne = “ywxtuv”
Production: NON
Explication:
La chaîne donnée “ywxtuv” est une sous-chaîne valide de S.

Approcher: On peut observer que chaque caractère suivant a une valeur inférieure Valeur ASCII que le caractère précédent sauf si ‘un’ est suivi par ‘z’. La meilleure façon de résoudre ce problème consiste simplement à vérifier pour chaque caractère si le caractère qui le suit a une valeur ASCII inférieure. Ignorez cette comparaison lorsque le caractère actuel est ‘a’. Si le caractère actuel ‘a’ s’est produit, vérifiez s’il est suivi du caractère ‘z’.

Voici les étapes :

  1. Créez une variable d’indicateur pour marquer si une chaîne donnée est une sous-chaîne valide ou non. Définissez-le initialement sur true.
  2. Parcourir la chaîne donnée chaîneet pour chaque caractère, chaîne[i] procédez comme suit :
    • Si chaîne[i+1] + 1 < chaîne[i]continuez la boucle.
    • Si chaîne[i] = ‘a’ et str[i+1] = ‘z’, continuez à nouveau avec la boucle.
    • Sinon, marquez la variable d’indicateur comme fausse et sortez de la boucle.
  3. Enfin, si le drapeau est true print OUI sinon imprimer NON.

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

C++

#include <iostream>

using namespace std;

void checkInfinite(string s)

{

    

    

    bool flag = 1;

    int N = s.length();

    

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

        

        

        if (s[i] == char(int(s[i + 1]) + 1)) {

            continue;

        }

        

        

        else if (s[i] == 'a'

                 && s[i + 1] == 'z') {

            continue;

        }

        

        

        else {

            flag = 0;

            break;

        }

    }

    

    if (flag == 0)

        cout << "NO";

    else

        cout << "YES";

}

int main()

{

    

    string s = "ecbaz";

    

    checkInfinite(s);

    return 0;

}

Java

class GFG{

public static void checkInfinite(String s)

{

    

    

    

    boolean flag = true;

    int N = s.length();

    

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

    {

        

        

        

        if (s.charAt(i) == (char)((int)

           (s.charAt(i + 1)) + 1))

        {

            continue;

        }

        

        

        else if (s.charAt(i) == 'a' &&

                 s.charAt(i + 1) == 'z')

        {

            continue;

        }

        

        

        else

        {

            flag = false;

            break;

        }

    }

    

    if (!flag)

        System.out.print("NO");

    else

        System.out.print("YES");

}

public static void main(String[] args)

{

    

    

    String s = "ecbaz";

    

    checkInfinite(s);

}

}

Python3

def checkInfinite(s):

    

    

    flag = 1

    N = len(s)

    

    for i in range(N - 1):

        

        

        if (s[i] == chr(ord(s[i + 1]) + 1)):

            continue

        

        

        elif (s[i] == 'a' and s[i + 1] == 'z'):

            continue

        

        

        else:

            flag = 0

            break

    

    if (flag == 0):

        print("NO")

    else:

        print("YES")

if __name__ == '__main__':

    

    s = "ecbaz"

    

    checkInfinite(s)

C#

using System;

class GFG{

public static void checkInfinite(String s)

{

    

    

    

    bool flag = true;

    int N = s.Length;

    

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

    {

        

        

        

        if (s[i] == (char)((int)

           (s[i + 1]) + 1))

        {

            continue;

        }

        

        

        else if (s[i] == 'a' &&

                 s[i + 1] == 'z')

        {

            continue;

        }

        

        

        else

        {

            flag = false;

            break;

        }

    }

    

    if (!flag)

        Console.Write("NO");

    else

        Console.Write("YES");

}

public static void Main(String[] args)

{

    

    

    String s = "ecbaz";

    

    checkInfinite(s);

}

}

Javascript

<script>

function checkInfinite(s)

{

    

    

    var flag = 1;

    var N = s.length;

    

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

        

        

        if (s[i] == String.fromCharCode((s[i + 1].charCodeAt(0)) + 1)) {

            continue;

        }

        

        

        else if (s[i] == 'a'

                 && s[i + 1] == 'z') {

            continue;

        }

        

        

        else {

            flag = 0;

            break;

        }

    }

    

    if (flag == 0)

        document.write( "NO");

    else

        document.write( "YES");

}

var s = "ecbaz";

checkInfinite(s);

</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 *