Machen Sie eine Zeichenfolge zu einem Nicht-Palindrom, indem Sie die angegebenen Zeichen einfügen

Problemstellung

In der Eingabe erhalten wir die Zeichenfolge str und das Zeichen c. Wir müssen das angegebene Zeichen c am Index in die Zeichenfolge einfügen, um die Zeichenfolge in ein Nicht-Palindrom umzuwandeln. Wenn wir die Zeichenfolge nicht in ein Nicht-Palindrom konvertieren können, geben Sie „-1“ aus.

Beispiel

Eintreten

str = ‘nayan’, c = ‘n’

Ausgabe

‘nnayan’

Die Übersetzung von

Erklärung

lautet:

Erklärung

Es kann mehrere Ausgabezeichenfolgen geben, da wir an jedem Index der angegebenen Zeichenfolge „n“ einfügen können. Daher kann die Ausgabezeichenfolge „nnayan“, „nanyan“, „naynan“, „nayann“ usw. sein.

Eintreten

str = ‘sss’, c = ‘s’

Ausgabe

‘-1’

Die Übersetzung von

Erklärung

lautet:

Erklärung

Egal, wo wir „s“ in die gegebene Zeichenfolge einfügen, es ist immer ein Palindrom.

Eintreten

str = ‘tutorialspoint’, c = ‘p’

Ausgabe

‘ptutorialspoint’

Die Übersetzung von

Erklärung

lautet:

Erklärung

Da str bereits kein Palindrom ist, wird die gleiche Zeichenfolge gedruckt, indem am ersten Index das Zeichen c eingefügt wird.

Die Logik zur Lösung des oben genannten Problems besteht darin, dass, wenn alle Zeichen in einer bestimmten Zeichenfolge dem angegebenen Zeichen c entsprechen, daraus kein Palindrom werden kann. Andernfalls fügen Sie an der ersten Position ein Zeichen hinzu und prüfen Sie, ob die resultierende Zeichenfolge ein Palindrom ist. Wenn ja, fügen Sie am Ende das angegebene Zeichen ein.

Methode 1

Bei dieser Methode verwenden wir eine while-Schleife, um zu prüfen, ob die gegebene Zeichenfolge ein Palindrom ist, und eine for-Schleife, um zu prüfen, ob alle Zeichen in der gegebenen Zeichenfolge gleich sind.

Algorithmus

• Schritt 1 – Initialisieren Sie die Variable „cnt“, um die Zeichenanzahl zu speichern, die dem angegebenen Zeichen c entspricht.

• Schritt 2 – Verwenden Sie eine for-Schleife, um über die Zeichenfolge zu iterieren. Wenn das Zeichen am Index i in der Zeichenfolge gleich dem Zeichen c ist, addieren Sie 1 zum Wert von „cnt“.

• Schritt 3 – Wenn der Wert von „cnt“ der Länge der Zeichenfolge entspricht, geben Sie „-1“ aus und führen Sie die Return-Anweisung aus.

• Schritt 4 − Initialisieren Sie eine „temp“-Variable mit c + str. Verwenden Sie anschließend die Funktion isPalindrome(), um zu überprüfen, ob die angegebene Zeichenfolge ein Palindrom ist.

• Schritt 5 – Definieren Sie die Funktion isPalindrome().

• Schritt 5.1 – Variable „links“ definieren und auf 0 initialisieren. Definieren Sie außerdem die Variable „right“ und initialisieren Sie sie auf die Länge der Zeichenfolge minus 1.

• Schritt 5.2 – Verwenden Sie eine While-Schleife und gleichen Sie die Zeichen am Anfang und Ende der Zeichenfolge ab. Erhöhen Sie außerdem den Wert der Variablen „links“ und verringern Sie den Wert der Variablen „rechts“.

• Schritt 5.3 – Wenn eine Nichtübereinstimmung gefunden wird, geben Sie „false“ zurück; andernfalls geben Sie „true“ zurück, wenn alle Schleifeniterationen abgeschlossen sind.

• Schritt 6 – Wenn der Wert der Variable „temp“ kein Palindrom ist, drucken Sie ihn andernfalls aus: str + c.

Die chinesische Übersetzung von

Beispiel

lautet:

Beispiel

#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;
}

Ausgabe

Non-palindromic string is: 
sasss

• Zeitkomplexität – O(N), weil wir eine for-Schleife verwenden, um die Gesamtzahl der Zeichen zu zählen, die dem angegebenen Zeichen entspricht.

• Raumkomplexität – O(1), da wir keinen zusätzlichen Raum nutzen.

Methode 2

Bei dieser Methode verwenden wir dieselbe Logik wie bei der ersten Methode, verwenden jedoch eine for-Schleife, um zu überprüfen, ob die Zeichenfolge ein Palindrom ist. Zusätzlich haben wir die Methode count() verwendet, um die Gesamtzahl der angegebenen Zeichen in der Zeichenfolge zu zählen.

Algorithmus

• Schritt 1 – Verwenden Sie die count()-Methode, übergeben Sie die Zeichenfolge als ersten Parameter und das angegebene Zeichen c als zweiten Parameter, um die Anzahl der Zeichen zu zählen, die dem angegebenen Zeichen in der Zeichenfolge entsprechen.

• Schritt 2 – Wenn der von der count()-Methode zurückgegebene Wert der Länge der Zeichenfolge entspricht, geben Sie „-1“ aus.

• Schritt 3 – Initialisieren Sie in der Funktion isPalindrome() „i“ auf 0 und „j“ auf die Länge der Zeichenfolge – 1. Danach verwendet der Benutzer eine Schleife, um die Start- und Endzeichen zu iterieren und zu vergleichen. Wenn eine Nichtübereinstimmung auftritt, geben Sie „false“ zurück.

• Schritt 4 - Fügen Sie das angegebene Zeichen an einer beliebigen Position ein und prüfen Sie, ob die Zeichenfolge kein Palindrom ist. Wenn die resultierende Zeichenfolge kein Palindrom ist, haben wir die Antwort. Andernfalls ändern Sie die Position des angegebenen Zeichens in der Zeichenfolge und überprüfen Sie erneut.

Die chinesische Übersetzung von

Beispiel

lautet:

Beispiel

#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;
}

Ausgabe

Non-palindromic string is: 
nnayan

• Zeitkomplexität - O(N)

• Raumkomplexität - O(1)

Fazit

Wir haben zwei Methoden kennengelernt, um eine bestimmte Zeichenfolge in eine nicht-palindromische Zeichenfolge umzuwandeln, d. h. das angegebene Zeichen an einer beliebigen Position einzufügen. Beide Methoden verwenden dieselbe Logik, aber in der ersten Methode haben wir eine manuelle Funktion geschrieben, um die Anzahl der gleichen Zeichen zu zählen, die dem angegebenen Zeichen entsprechen, während wir in der zweiten Methode die Methode count() verwendet haben.

Die erste Methode eignet sich eher für Lernzwecke und die zweite Methode eignet sich eher für die Echtzeitentwicklung.

Das obige ist der detaillierte Inhalt vonMachen Sie eine Zeichenfolge zu einem Nicht-Palindrom, indem Sie die angegebenen Zeichen einfügen. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!