Créez une chaîne non palindrome en insérant les caractères donnés

Énoncé du problème

Nous recevons la chaîne str et le caractère c en entrée. Nous devons insérer le caractère c donné dans la chaîne à l'index afin de convertir la chaîne en un non-palindrome. Si nous ne pouvons pas convertir la chaîne en un non-palindrome, imprimez "-1".

Exemple

Entrez

str = ‘nayan’, c = ‘n’

Sortie

‘nnayan’

La traduction de

Explication

est :

Explication

Il peut y avoir plusieurs chaînes de sortie car nous pouvons insérer « n » à n'importe quel index de la chaîne donnée. Par conséquent, la chaîne de sortie peut être « nnayan », « nanyan », « naynan », « nayann », etc.

Entrez

str = ‘sss’, c = ‘s’

Sortie

‘-1’

La traduction de

Explication

est :

Explication

Peu importe où nous insérons un « s » dans la chaîne donnée, c'est toujours un palindrome.

Entrez

str = ‘tutorialspoint’, c = ‘p’

Sortie

‘ptutorialspoint’

La traduction de

Explication

est :

Explication

Puisque str est déjà un non-palindrome, il imprime la même chaîne en insérant le caractère c au premier index.

La logique pour résoudre le problème ci-dessus est que si tous les caractères d'une chaîne donnée sont égaux au caractère c donné, cela ne peut pas en faire un palindrome. Sinon, ajoutez un caractère en première position et vérifiez si la chaîne résultante est un palindrome. Si tel est le cas, insérez le caractère donné à la fin.

Méthode 1

Dans cette méthode, nous utilisons la boucle while pour vérifier si la chaîne donnée est un palindrome et la boucle for pour vérifier si tous les caractères de la chaîne donnée sont identiques.

Algorithme

• Étape 1 - Initialisez la variable "cnt" pour stocker le nombre de caractères égal au caractère c donné.

• Étape 2 - Utilisez une boucle for pour parcourir la chaîne. Si le caractère à l'index i dans la chaîne est égal au caractère c, ajoutez 1 à la valeur de "cnt".

• Étape 3 - Si la valeur de 'cnt' est égale à la longueur de la chaîne, imprimez '-1' et exécutez l'instruction return.

• Étape 4 - Initialisez une variable 'temp' en utilisant c + str. Après cela, utilisez la fonction isPalindrome() pour vérifier si la chaîne donnée est un palindrome.

• Étape 5 - Définissez la fonction isPalindrome().

• Étape 5.1 - Définissez la variable 'left' et initialisez-la à 0. Définissez également la variable 'right' et initialisez-la à la longueur de la chaîne moins 1.

• Étape 5.2 - Utilisez une boucle while et faites correspondre les caractères au début et à la fin de la chaîne. De plus, augmentez la valeur de la variable « gauche » et diminuez la valeur de la variable « droite ».

• Étape 5.3 - Si une incompatibilité est trouvée, renvoyez false ; sinon, renvoyez true lorsque toutes les itérations de boucle sont terminées.

• Étape 6 - Si la valeur de la variable "temp" n'est pas palindrome, imprimez-la sinon, imprimez str + c.

La traduction chinoise de

Exemple

est :

Exemple

#include <bits/stdc++.h>
using namespace std;
// Function to check if a string is a palindrome
bool isPalindrome(string str) {
   int left = 0;
   int right = str.length() - 1;
   // Keep comparing characters while they are the same
   while (right > left) {
      if (str[left++] != str[right--]) {
         return false;
      }
   }
   return true;
}
// Function to make a string non-palindrome by adding a character
void makeNonPalindrome(string str, char c) {
   int cnt = 0;
   for (int i = 0; i < str.length(); i++) {
      if (str[i] == c) {
         cnt++;
      }
   }
   if (cnt == str.length()) {
      cout << "-1";
      cout << "We can convert the string into a non-palindromic string by adding a given character at any position.";
      return;
   }
   cout << "Non-palindromic string is: " << endl;
   // append the character at the start, and check if it is a palindrome
   string temp = c + str;
   if (!isPalindrome(temp)){
      cout << temp << endl;
   } else {
      cout << str + c << endl;
   }
}
int main(){
   string str = "sass";
   char c = 's';
   makeNonPalindrome(str, c);
   return 0;
}

Sortie

Non-palindromic string is: 
sasss

• Complexité temporelle - O(N) car nous utilisons une boucle for pour compter le nombre total de caractères égal au caractère donné.

• Complexité spatiale - O(1) puisque nous n'utilisons aucun espace supplémentaire.

Méthode 2

Dans cette méthode, nous utilisons la même logique que dans la première méthode, mais nous utilisons une boucle for pour vérifier si la chaîne est un palindrome. De plus, nous avons utilisé la méthode count() pour compter le nombre total de caractères donnés dans la chaîne.

Algorithme

• Étape 1 - Utilisez la méthode count(), en passant la chaîne comme premier paramètre et le caractère donné c comme deuxième paramètre pour compter le nombre de caractères égal au caractère donné dans la chaîne.

• Étape 2 - Si la valeur renvoyée par la méthode count() est égale à la longueur de la chaîne, imprimez "-1".

• Étape 3 - Dans la fonction isPalindrome(), initialisez 'i' à 0 ​​et 'j' à la longueur de la chaîne - 1. Après cela, l'utilisateur utilise une boucle pour parcourir et comparer les caractères de début et de fin. En cas de non-concordance, renvoyez false.

• Étape 4 - Insérez le caractère donné à n'importe quelle position et vérifiez si la chaîne n'est pas palindrome. Si la chaîne résultante est un non-palindrome, nous avons la réponse ; sinon, changez la position du caractère donné dans la chaîne et vérifiez à nouveau.

La traduction chinoise de

Exemple

est :

Exemple

#include <bits/stdc++.h>
using namespace std;
// Function to check if a string is a palindrome
bool isPalindrome(string str) {
   // Start from the leftmost and rightmost corners of str
   for (int i = 0, j = str.length() - 1; i < j; i++, j--){
      // If there is a mismatch, then the string is not palindrome; return false.
      if (str[i] != str[j])
         return false;
   }
   return true;
}
// Function to make a string non-palindrome by adding a character
void makeNonPalindrome(string str, char c){
   //   if all characters are the same as a given character, then the string cannot be made non-palindrome
   if (count(str.begin(), str.end(), c) == str.length()) {
      cout << "-1";
      cout << "We can convert the string into a non-palindromic string by adding a given character at any position.";
      return;
   }
   cout << "Non-palindromic string is: " << endl;
   // append the character at the start, and check if it is a palindrome
   string temp = c + str;
   if (!isPalindrome(temp)){
      cout << temp << endl;
   } else {
      cout << c + str << endl;
   }
}
int main() {
   string str = "nayan";
   char c = 'n';
   makeNonPalindrome(str, c);
   return 0;
}

Sortie

Non-palindromic string is: 
nnayan

• Complexité temporelle - O(N)

• Complexité spatiale - O(1)

Conclusion

Nous avons appris deux méthodes pour convertir une chaîne donnée en une chaîne non palindromique, c'est-à-dire insérer le caractère donné à n'importe quelle position. Les deux méthodes utilisent la même logique mais dans la première méthode, nous avons écrit une fonction manuelle pour compter le nombre de caractères identiques qui sont égaux au caractère donné tandis que dans la deuxième méthode, nous avons utilisé la méthode count().

La première méthode est plus adaptée à des fins d'apprentissage et la deuxième méthode est plus adaptée au développement en temps réel.

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!