Vérifie si une chaîne peut être divisée en trois sous-chaînes, où une sous-chaîne est une sous-chaîne des deux autres sous-chaînes

Dans ce problème, nous devons diviser la chaîne donnée afin que la troisième sous-chaîne puisse être une sous-chaîne des deux premières sous-chaînes.

Pensons à une solution. La troisième chaîne peut être une sous-chaîne des deux premières chaînes uniquement si les deux premières chaînes contiennent tous les caractères de la troisième chaîne. Nous devons donc trouver au moins un caractère dans la chaîne donnée avec une fréquence supérieure à 3, et nous pouvons prendre la troisième sous-chaîne de ce caractère unique.

Énoncé du problème - On nous donne une chaîne str contenant N caractères alphabétiques minuscules. Nous devons vérifier si nous pouvons diviser la chaîne en trois sous-chaînes a, b et c de telle sorte que la sous-chaîne c soit une sous-chaîne de a et b. Imprimez "oui" ou "non" selon que 3 sous-chaînes peuvent être trouvées.

Exemple

Input –  str = "tutorialsPoint"

Output – ‘Yes’

Instructions

Ici, nous pouvons diviser la chaîne en "tu", "torialsPoin" et "t". La troisième chaîne est donc une sous-chaîne des deux premières chaînes.

Input –  str = "tutorials"

Output – ‘No’

Instructions

Nous ne pouvons pas diviser la chaîne en trois sous-chaînes en fonction de la condition donnée car la fréquence d'un caractère n'est pas supérieure à 3.

Input –  str = "hhhhhhhh"

Output – ‘Yes’

Instructions

Selon les conditions données, les trois sous-chaînes peuvent être « h », « h » et « hhhhhh ».

Méthode 1

Dans cette méthode, nous utiliserons un tableau pour stocker la fréquence de chaque caractère. Après cela, nous vérifierons les caractères dont la fréquence est supérieure ou égale à 3.

Algorithme

• Étape 1 - Définissez le tableau "freq" d'une longueur égale à 26.

• Étape 2 - Parcourez la chaîne pour compter la fréquence des caractères. Dans la boucle for, incrémentez la valeur de freq[str[i] – 'a']. Ici, str[i] – 'a' donne un index compris entre 0 et 26.

• Étape 3 - Maintenant, parcourez le tableau "freq" et renvoyez vrai si la valeur d'un index du tableau est supérieure à "3".

• Étape 4 - Renvoie true lorsque la boucle se termine.

• Étape 5 - Imprimez "Oui" ou "Non" en fonction de la valeur de retour de la fonction isSUbStringPossible().

Exemple

#include <bits/stdc++.h>
using namespace std;
// function to Check if a string can be split into 3 substrings such that one of them is a substring of the other two
string isSubStringPossible(string str, int len){

   // array to store the frequency
   int freq[26] = {0};
   
   // Iterate over the string
   for (int i = 0; i < len; i++){
   
      // count the frequency of each character
      freq[str[i] - 'a']++;
   }
   
   // Traverse the frequency array
   for (int i = 0; i < 26; i++){
   
      // If the frequency of any character is greater than or equal to 3, then return "Yes."
      if (freq[i] >= 3){
         return "Yes";
      }
   }
   
   // Otherwise
   return "No";
}
int main(){
   string str = "tutorialsPoint";
   int len = str.length();
   cout << "The given string can be splited into 3 substrings such that one of them is a substring of the other two - " << isSubStringPossible(str, len);
   return 0;
}

Sortie

The given string can be splited into 3 substrings such that one of them is a substring of the other two - Yes

Complexité temporelle - O(N), lorsque nous parcourons la chaîne.

Complexité spatiale - O(1) car nous utilisons des tableaux de longueur constante.

Méthode 2

Dans cette méthode, nous convertissons d'abord la chaîne en un tableau de caractères. Après cela, nous utilisons la méthode count() pour compter la fréquence de caractères spécifiques dans le tableau.

Algorithme

• Étape 1 - Créez un tableau de taille "len + 1", où "len" est la longueur de la chaîne.

• Étape 2 - Copiez la chaîne dans un tableau de caractères à l'aide de la méthode strcpy().

• Étape 3 - Utilisez une boucle for pour un total de 26 itérations.

• Étape 4 - Dans la boucle for, utilisez la méthode count() pour compter le nombre d'occurrences d'un caractère spécifique.

La méthode

count() prend une référence à la position de départ comme premier argument, une référence à la position de fin comme deuxième argument et un caractère comme troisième argument.

Ici, nous devons passer la valeur ASCII du caractère comme paramètre et nous utilisons I + 'a' pour obtenir la valeur.

• Étape 5 - Renvoie true si la méthode count() renvoie supérieur ou égal à 3.

• Étape 6 - Renvoie false lorsque la boucle se termine.

Exemple

#include <bits/stdc++.h>
using namespace std;
// function to Check if a string can be split into 3 substrings such that one of them is a substring of the other two
string isSubStringPossible(string str, int len){

   //    converting str to char array.
   char char_array[len + 1];
   
   // copy string to char array
   strcpy(char_array, str.c_str());
   
   // make 26 iterations
   for (int i = 0; i < 26; i++){
   
      // Using count() to count the occurrence of each character in the array, and return 'yes' if any character occurs more than 2 times.
      if (count(char_array, char_array + len, i + 'a') >= 2)
         return "YES";
   }
   return "NO";
}
int main(){
   string str = "tutorials";
   int len = str.length();
   cout << "The given string can be splited into 3 substrings such that one of them is a substring of the other two - " << isSubStringPossible(str, len);
   return 0;
}

Sortie

The given string can be splited into 3 substrings such that one of them is a substring of the other two - Yes

Complexité temporelle - O(N) car la méthode count() parcourt le tableau de caractères pour compter le nombre de caractères. De plus, la méthode strcpy() prend un temps O(N).

Complexité spatiale - O(N) car nous stockons la chaîne dans un tableau de caractères.

Conclusion

Nous avons appris deux façons de diviser une chaîne en trois sous-chaînes afin qu'une sous-chaîne puisse être la sous-chaîne de deux autres sous-chaînes. Le code de la deuxième méthode est plus lisible et convivial pour les débutants, mais il est plus coûteux en temps et en espace.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!