Prüfen, ob eine Zeichenkette ein Palindrom in Java ist

1. Verwenden Sie Zeiger, um zu überprüfen, ob ein String ein Palindrom in Java ist
2. Kehren Sie den String um, um zu prüfen, ob ein String ein Palindrom in Java ist
3. Verwenden Sie Rekursion, um zu prüfen, ob ein String ein Palindrom in Java ist
4. Fazit

Wenn die Zeichen einer Zeichenkette von rechts nach links gleich sind wie die Zeichen der Zeichenkette von links nach rechts, dann spricht man von einem Palindrom. Beispiele sind Zeichenketten wie ababa, radar und ppqpp.

Hier ist das erste Zeichen dasselbe wie das letzte Zeichen; das zweite Zeichen ist das gleiche wie das vorletzte Zeichen usw. In diesem Artikel werden wir uns die verschiedenen Java-Programme ansehen, um zu überprüfen, ob ein String ein Palindrom ist oder nicht.

Verwenden Sie Zeiger, um zu überprüfen, ob ein String ein Palindrom in Java ist

Eine sehr einfache Idee, um zu überprüfen, ob ein String ein Palindrom ist oder nicht, besteht darin, zwei Zeiger zu verwenden; Ein Punkt zeigt auf den Anfang der Zeichenfolge und der andere auf das Ende der Zeichenfolge. Betrachten Sie den folgenden Code.

public class PalProgram {
  static boolean PalFunc(String s)

  {
    // Pointer i pointing to the start and j pointing to the end
    int i = 0, j = s.length() - 1;

    while (i < j) {
      // Check if there is any mis-matching pair
      if (s.charAt(i) != s.charAt(j))
        return false;

      // Update the pointers
      i++;
      j--;
    }

    // If no mismatch occurs
    return true;
  }

  public static void main(String[] args) {
    String s = "ava";
    s = s.toLowerCase();
    if (PalFunc(s))
      System.out.print("Yes, it is a palindrome.");

    else
      System.out.print("No, it is not a palindrome.");
  }
}

Ausgabe:

Yes, it is a palindrome.

Hier zeigt innerhalb der Funktion PalFunc der erste Zeiger i auf den Anfang des Strings und der zweite Zeiger j auf das Ende des Strings, was wir prüfen müssen, ob es sich um ein Palindrom handelt oder nicht.

Dann laufen wir eine Schleife bis i<j. Bei jedem Schritt prüfen wir, ob die Zeichen, auf die diese beiden Zeiger zeigen, i und j, übereinstimmen oder nicht.

Außerdem inkrementieren wir gleichzeitig i und dekrementieren j um eins. Wenn die Zeichen in keinem Schritt übereinstimmen, geben wir false zurück und benachrichtigen den Benutzer, dass die Zeichenfolge kein Palindrom ist.

In unserem Beispiel verwenden wir die Funktion toLowerCase(). Der Java-Compiler vergleicht zwei Zeichen anhand ihrer ASCII-Werte.

Das bedeutet, dass A == a als false ausgewertet wird. In diesem Fall wird die Zeichenfolge abA in Java nicht als Palindrom betrachtet, was nicht das eigentliche Szenario ist.

Aus diesem Grund müssen wir den String vor dem Vergleich in der for-Schleife zuerst in Groß- oder Kleinbuchstaben umwandeln. Es ist hilfreich bei Palindromen wie AVva, wo die Zeichen Groß- und Kleinschreibung mischen.

Kehren Sie den String um, um zu prüfen, ob ein String ein Palindrom in Java ist

Bedenken Sie, dass wir den String aabcvbaa haben. Lassen Sie uns zuerst die Zeichenfolge umkehren. Die resultierende Zeichenfolge ist aabvcbaa.

Das letzte Zeichen der ursprünglichen Zeichenfolge wird zum ersten Zeichen der umgekehrten Zeichenfolge. Das vorletzte Zeichen der ursprünglichen Zeichenfolge wird zum zweiten Zeichen der umgekehrten Zeichenfolge und so weiter.

Jetzt können wir die beiden Zeichenketten Zeichen für Zeichen vergleichen, um zu prüfen, ob es sich bei der Zeichenkette um ein Palindrom handelt. Wenn eine Nichtübereinstimmung auftritt, ist die Zeichenfolge kein Palindrom, und wir können false zurückgeben, wodurch der Benutzer benachrichtigt wird, dass die Zeichenfolge kein Palindrom ist.

Wenn jedoch durchgehend keine Abweichung auftritt, können wir true zurückgeben und sagen, dass die Zeichenfolge ein Palindrom ist. In diesem Fall erstellen wir eine neue umgekehrte Zeichenfolge, anstatt zwei Zeiger in derselben Zeichenfolge zu verwenden (siehe Demonstration).

Manchmal dürfen wir in Java bereitgestellte eingebaute Funktionen nicht verwenden. Daher werden wir die reverse()-Methode von Java-APIs nicht verwenden.

Wir werden unsere Funktion schreiben, um die Zeichenfolge umzukehren.

public class Solution {
  static boolean Sol(String s)

  {
    // reverse the string
    StringBuilder reversed_str = new StringBuilder();
    char[] newArray = s.toCharArray();
    for (int index = newArray.length - 1; index >= 0; index--) {
      reversed_str.append(newArray[index]);
    }

    // comparing the original string with the reversed string
    return (reversed_str.toString()).equals(s);
  }

  public static void main(String[] args) {
    String s = "raceCAR";

    // Convert the string to the lowercase
    s = s.toLowerCase();

    if (Sol(s))
      System.out.print("Yes, this string is a palindrome.");

    else
      System.out.print("No, it isn't a palindrome.");
  }
}

Ausgabe:

Yes, this string is a palindrome.

Lassen Sie uns schnell sehen, was in der Funktion Sol passiert. Wir ändern den String zuerst in ein Array und verwenden dies dann, um den String umzukehren.

Dann vergleichen wir die umgekehrte Zeichenfolge Buchstabe für Buchstabe mit der ursprünglichen Zeichenfolge.

1. Klasse StringBuilder: Die String-Klasse in Java erzeugt unveränderliche Strings, also unveränderliche Strings. Hier wollen wir einen String erstellen, reversed_str, der veränderbar ist, um Zeichen daran anzuhängen. Die Klasse StringBuilder in Java hilft uns, veränderbare Strings zu erstellen.
2. Methode toCharArray: Da wir den ursprünglichen und den umgekehrten String zeichenweise vergleichen wollen, verwenden wir die Methode toCharArray(), um den String in eine Reihe von Zeichen umzuwandeln. Das Ergebnis speichern wir im Array newArray.
3. Methode append(): Nachdem Sie die ursprüngliche Zeichenfolge in ein Zeichenarray geändert haben, verwenden Sie sie, um die umgekehrte Zeichenfolge zu erstellen. Dazu durchlaufen wir das Zeichen-Array vom Ende her und fügen die Zeichen im String reversed_str mit der Methode append() immer wieder hinzu.
4. Methode toString(): Wir ändern es wieder in einen String, indem wir die toString()-Methode verwenden, nachdem wir den umgekehrten String erstellt haben. Wir tun dies, weil wir zwei Strings einfach mit der Methode equals() vergleichen können.

5. Methode equals(): Zuletzt vergleichen wir den ursprünglichen String s mit dem umgekehrten String reversed_str. Dazu können wir die Methode equals() verwenden, die true zurückgibt, wenn alle Zeichen des Strings übereinstimmen.

Dasselbe können wir mit Leichtigkeit erreichen, wenn wir die Methode reverse() der Java-APIs verwenden – StringBuilder und StringBuffer, wie unten gezeigt.

// Check if a string is a palindrome
// Java program

public class Solution {
  static boolean Sol(String s)

  { // Using the stringbuilder API
    StringBuilder newString = new StringBuilder(s);
    StringBuilder rev_str = newString.reverse();
    return (rev_str.toString()).equals(s);
  }

  public static void main(String[] args) {
    String s = "raceCAR";

    // Convert the string to the lowercase
    s = s.toLowerCase();

    if (Sol(s))
      System.out.print("Yes, it is a palindrome.");

    else
      System.out.print("No, it is not a palindrome.");
  }
}

Ausgabe:

Yes, it is a palindrome.

Beachten Sie, dass wir bei Verwendung der StringBuilder-API keine Zeichen-Arrays erstellen oder den String mit einer for-Schleife umkehren müssen. Diese Methode ist sauber und einfach.

Um mehr über die Klasse StringBuilder zu erfahren, lesen Sie [diese Dokumentation] (https://docs.oracle.com/javase/7/docs/api/java/lang/StringBuilder.html).

Wir können auch die StringBuilder-API verwenden, wie unten gezeigt.

public class CheckPalindrome {
  static boolean Sol(String s)

  { // Using the stringbuffer API
    StringBuffer str = new StringBuffer(s);
    StringBuffer rev_str = str.reverse();
    return (rev_str.toString()).equals(s);
  }

  public static void main(String[] args) {
    String s = "raceCAR";

    // Convert the string to the lowercase
    s = s.toLowerCase();

    if (Sol(s))
      System.out.print("Yes, it is a palindrome.");

    else
      System.out.print("No, it is not a palindrome.");
  }
}

Ausgabe:

Yes, it is a palindrome.

Sie fragen sich vielleicht, was die Klassen StringBuilder und StringBuffer unterscheidet, weil der Code identisch aussieht.

Die Klasse StringBuffer erlaubt nur jeweils einem Thread, diese Methode aufzurufen. Es ist synchronisiert.

Andererseits kann die Methode StringBuilder von mehreren Threads gleichzeitig aufgerufen werden. Es ist nicht synchronisiert.

Allerdings ist die Klasse StringBuilder effizienter als die Klasse StringBuffer. Um mehr über die Klasse StringBuffer zu erfahren, lesen Sie [diese Dokumentation].

Verwenden Sie Rekursion, um zu prüfen, ob ein String ein Palindrom in Java ist

Wir können die Funktion Sol rekursiv aufrufen, um zu prüfen, ob ein String ein Palindrom ist. Die Grundidee besteht darin, die Rekursion zum Iterieren über die Zeichenfolge zu verwenden.

public class Solution {
  static boolean Sol(String s)

  {
    s = s.toLowerCase();
    return RecursePal(s, 0, s.length() - 1);
  }

  static boolean RecursePal(String s, int f, int b) {
    if (f == b) {
      return true;
    }
    if ((s.charAt(f)) != (s.charAt(b))) {
      return false;
    }
    if (f < b + 1) {
      return RecursePal(s, f + 1, b - 1);
    }
    return true;
  }

  public static void main(String[] args) {
    String s = "raceCAR";

    // Convert the string to the lowercase
    s = s.toLowerCase();

    if (Sol(s))
      System.out.print("Yes");

    else
      System.out.print("No");
  }
}

Ausgabe:

Yes

Hier definieren wir eine Funktion, RecursePal. Als Argumente übergeben wir den String s, den Index des ersten Zeichens als f und den Index des letzten Zeichens als b.

Dann prüfen wir, ob das Zeichen bei f dasselbe ist wie bei b. Wenn ja, geben wir true zurück.

Andernfalls geben wir false zurück. Zuletzt rufen wir erneut die Funktion RecursePal auf, um diesen Vorgang für den gesamten String zu wiederholen.

Jedes Mal, wenn wir diese Funktion rekursiv aufrufen, erhöhen wir den Index f und verringern den Index b um eins.

Fazit

In diesem Tutorial haben wir die verschiedenen Möglichkeiten in Java gesehen, um zu überprüfen, ob eine Zeichenfolge ein Palindrom ist oder nicht.

Wir haben gelernt, wie man Zwei-Zeiger verwendet, um den String in beide Richtungen zu durchlaufen. Wir haben auch gesehen, wie man überprüft, ob ein String ein Palindrom ist, indem man den String umkehrt und Rekursion in Java verwendet.