Finden Sie das erste sich wiederholende Zeichen in einer Zeichenfolge in C++

1. Finden Sie das erste sich wiederholende Zeichen in einer Zeichenfolge in C++
2. Verwenden Sie die Hashing-Technik, um das erste sich wiederholende Zeichen in einer Zeichenfolge in C++ zu finden
3. Verwenden Sie die Brute-Force-Methode, um das erste sich wiederholende Zeichen in einer Zeichenfolge in C++ zu finden

In diesem Tutorial erfahren Sie, wie Sie das erste sich wiederholende Zeichen in einer Zeichenfolge in C++ finden. Sie lernen drei Ansätze kennen, um diesen Zweck zu erfüllen: die Hashing-Technik, die Brute-Force-Methode und das Schreiben Ihres Algorithmus.

Finden Sie das erste sich wiederholende Zeichen in einer Zeichenfolge in C++

Es gibt zwei Ansätze, um zu versuchen, Ihre Algorithmen zu schreiben; Der erste Ansatz besteht darin, die Zeichenfolge von links nach rechts zu durchlaufen, und der zweite Ansatz besteht darin, die Zeichenfolge von rechts nach links zu durchlaufen und die besuchten Zeichen zu verfolgen. Der zweite Ansatz ist allen anderen in der Leistung überlegen, da er effizienter ist, da er weniger Vergleiche durchführt.

Sortieralgorithmen können Ihnen helfen, das erste sich wiederholende Zeichen in einer Zeichenfolge in O(n Log n)-Zeiten zu finden. Sie können jedoch die Zeichenfolge durchlaufen und die Zeichen mit ASCII-Codes hashen, die Schleife auf dem Hash-Array ausführen und die minimale Position jedes wiederholten Zeichens finden.

Codebeispiel:

#include <iostream>

using namespace std;

#define numberChar 256

// left most string
int farLeftStr(string& primeStr) {
  // represents the first index
  int IndexNum[numberChar];

  for (int i = 0; i < numberChar; i++) IndexNum[i] = -1;

  // represents the resultIndexNum
  int resultStr = INT_MAX;

  for (int i = 0; i < primeStr.length(); i++) {
    if (IndexNum[primeStr[i]] == -1)
      IndexNum[primeStr[i]] = i;
    else
      resultStr = min(resultStr, IndexNum[primeStr[i]]);
  }
  return (resultStr == INT_MAX) ? -1 : resultStr;
}

int main() {
  string primeStr = "HouseOfTheDragons";
  int left = farLeftStr(primeStr);

  if (left == -1)
    cout << "All characters are distinct or string is empty ";
  else
    cout << "The first repeating character is: " << primeStr[left];
  return 0;
}

Ausgang:

The first repeating character is: o

Das Durchlaufen einer Zeichenfolge von links nach rechts ist möglich, wenn der erste Index jedes Zeichens mit -1 initialisiert wird. Sie können den ersten oder ganz linken Index eines wiederholten Zeichens (falls Sie darauf stoßen) mit dem aktuellen Ergebnis vergleichen.

Darüber hinaus können Sie dieses Problem mit der Komplexität von O(N²) lösen, indem Sie jedes Zeichen untersuchen und im Rest der Zeichenfolge danach suchen.

Verwenden Sie die Hashing-Technik, um das erste sich wiederholende Zeichen in einer Zeichenfolge in C++ zu finden

Ein Count-Array kann das erste sich wiederholende Zeichen finden und die Anzahl der sich wiederholenden Zeichen in einer Zeichenfolge speichern.

Die Hashing-Technik besteht aus vier Hauptschritten.

1. Erstellen einer Hash-Tabelle.
2. Zeichen scannen.
3. Fügen Sie ein Zeichen in die Hash-Tabelle ein, falls es nicht vorhanden ist.
4. Anderenfalls Rückgabe dieses Zeichens als Duplikat.

Codebeispiel:

#include <iostream>

// hashing function object type
#include <unordered_set>

using namespace std;

char getRepeatingChar(string &str) {
  unordered_set<char> hashObj;

  for (int i = 0; i < str.length(); i++) {
    char repChar = str[i];
    if (hashObj.find(repChar) != hashObj.end())
      return repChar;
    else
      hashObj.insert(repChar);
  }
  return '\0';
}

int main() {
  string expStr = "GameOfThrones";
  cout << "The first repeating character is: " << getRepeatingChar(expStr);
}

Ausgang:

The first repeating character is: e

Eine andere bekannte Variante dieses Problems ist das Drucken des ersten eindeutigen oder sich nicht wiederholenden Zeichens in einer Zeichenfolge, indem die Ergebnisse gedruckt werden, wenn der Count gleich eins ist. Es ist möglich, alle sich wiederholenden Zeichen in einer Zeichenfolge als erweiterte Variation der ursprünglichen Technik zu drucken, aber es ist nicht so einfach wie die grundlegende Hashing-Methode.

Da der Benutzer das Array Count erstellen muss, beträgt die Zeitkomplexität dieser Methode O(n). Im schlimmsten Fall, ohne Wiederholung und zusätzlichen Platz, wird seine zeitliche Komplexität O(1) sein.

Verwenden Sie die Brute-Force-Methode, um das erste sich wiederholende Zeichen in einer Zeichenfolge in C++ zu finden

Es ist eine einfache Methode, die es Programmierern ermöglicht, jedes Zeichen einer Zeichenfolge zu überprüfen, um ein sich wiederholendes Zeichen zu finden, und die entsprechenden Ergebnisse auszugeben. Wenn die Endzeichenfolge erreicht oder das letzte Zeichen gescannt wird, wird kein sich wiederholendes Zeichen gefunden, und es gibt standardmäßig kein sich wiederholendes Zeichen.

Im schlimmsten Fall beträgt seine Zeitkomplexität O(n2) bei keiner Wiederholung, im besten Fall O(1), was das Vorhandensein eines sich wiederholenden Zeichens an der zweiten Position darstellt . Da Sie ein Zählarray benötigen, das eine konstante Menge an Speicher benötigt, ist es mehr als die Brute-Force-Methode, und der gesamte zusätzliche Speicherplatz, den es benötigt, ist O(1), dh konstant.

Codebeispiel:

#include <iostream>

using namespace std;

int main() {
  string expStr = "Hello World!";
  string primeExp = "";

  // check the boundary of the `expStr` string
  if (expStr == primeExp) {
    cout << "The string is empty!";
  }

  for (int a = 0; expStr[a] != '\0'; a++) {
    for (int b = a + 1; expStr[b] != '\0'; b++) {
      if (expStr[a] == expStr[b]) {
        cout << "The first repeating character is: " << expStr[a];
      }
      break;
    }
  }
}

Ausgang:

The first repeating character is: l