Überprüfen Sie für Palindrom rekursiv

Habe ich eine Klasse, die prüft, ob ein string ein Palindrom ist oder nicht. Ich habe zwei Fragen.

1) Ist dies der effizienteste Weg, um zu überprüfen, für Palindrom?
2) Kann dies umgesetzt werden rekursiv?

public class Words {

    public static boolean isPalindrome(String word) {
    String pal = null;
    word = word.replace(" ", "");
    pal = new StringBuffer(word).reverse().toString();
    if (word.compareTo(pal) == 0) {
        return true;
    } else {
        return false;
    }

    }

}

Haben eine test-Klasse, um dies zu testen... Zweifel gebraucht, aber hier ist es sowieso, wenn jemand kümmert sich um zu versuchen, es aus zu sein in der Lage, mir zu helfen, mit jedem der beiden oben genannten Fragen...

public class testWords {

    public static void main(String[] args) {
    if (Words.isPalindrome("a") == true) {
        System.out.println("true");
    } else {
        System.out.println("false");
    }
    if (Words.isPalindrome("cat") == true) {
        System.out.println("true");
    } else {
        System.out.println("false");
    }
    if (Words.isPalindrome("w o    w") == true) {
        System.out.println("true");
    } else {
        System.out.println("false");
    }
    if (Words.isPalindrome("   a  ") == true) {
        System.out.println("true");
    } else {
        System.out.println("false");
    }
    if (Words.isPalindrome("mom!") == true) {
        System.out.println("true");
    } else {
        System.out.println("false");
    }

    }

}

vielen Dank im Voraus für jede Hilfe und oder-Eingang 🙂

Die man vielleicht ändern möchte, was für Sie gültige Zeichen bei der Entscheidung, ob ein Satz ein Palindrom ist. Zum Beispiel, "Madam, ich bin Adam" ist ein Palindrom.
also sollte ich versuchen, mein Programm zu ignorieren Zeichen wie "' "
stackoverflow.com/questions/1579977/...
Zunächst herauszufiltern, die nicht-alphanumerische Zeichen enthalten, prüfen Sie, ob es ein Palindrom ist.
return (word.compareTo(pal) == 0) spart auf die if.

InformationsquelleAutor choloboy7 | 2013-03-30

  1. 7

    Zur Umsetzung einer 'palindrome check' rekursiv ist, müssen Sie vergleichen, wenn das erste und das Letzte Zeichen sind die gleichen. Wenn Sie sind nicht identisch die Zeichenfolge ist sicherlich nicht ein Palindrom. Wenn Sie die gleiche Zeichenfolge könnte ein Palindrom ist, müssen Sie vergleichen die 2. Charakter mit dem 2. bis zum letzten Zeichen, und so weiter, bis Sie strikt weniger als 2 Zeichen, die aber noch geprüft werden, in Ihrem string.

    Einen rekursiven Algorithmus würde dann so Aussehen:

    public static boolean isPalindrome(String word) {
  //Strip out non-alphanumeric characters from string
  String cleanWord = word.replaceAll("[^a-zA-Z0-9]","");
  //Check for palindrome quality recursively
  return checkPalindrome(cleanWord);
}
private static boolean checkPalindrome(String word) {
  if(word.length() < 2) { return true;  }
  char first  = word.charAt(0);
  char last   = word.charAt(word.length()-1);
  if(  first != last  ) { return false; }
  else { return checkPalindrome(word.substring(1,word.length()-1)); }
}

    • Hinweis, dass mein Rekursion Methode ist nicht der effizienteste Ansatz, aber
      einfach zu verstehen

    • Marimuthu Madasamy hat eine effizientere rekursive Methode, ist aber schwerer zu verstehen

    • Joe F aufgeführt hat, ein äquivalent effiziente iterative Methode

      das ist die besten Ansatz für die Implementierung, da es nicht die Ursache für - stack overflow Fehler
    +1 Das scheint korrekt zu sein, würden Sie bitte erklären, um OP, warum das funktioniert?
    Ich denke du meinst word.length() < 2 für Ihre base case.
    Sie sind richtig, vielen Dank für das Auffinden der typo
    Verdammt, dachte ich, ich Feste, dass internalPalindromeCheck sollte die checkPalindrome Methode.
    die word.replaceAll("[^a-zA-Z0-9]",""); ist ein statement, erzählen java, um die Zeichenfolge in Anspruch nehmen, finden alle nicht alphanumerischen Zeichen, und ersetzen Sie Sie durch eine leere Zeichenkette. Der verwirrende Teil ich nehme an der "[^a-zA-Z0-9]". Dies nennt man eine Regulärer Ausdruck (RegEx), sind Sie ein leistungsfähiges und vielseitiges Werkzeug. Definitiv lohnt sich zu lernen in der Zeit.

    InformationsquelleAutor recursion.ninja

  2. 6

    Hier ist eine weitere rekursive Lösung aber mit array, das könnte Ihnen einige performance-Vorteil gegenüber den string in rekursive Aufrufe (wobei substring oder charAt).

    private static boolean isPalindrome(final char[] chars, final int from,
        final int to) {
    if (from > to) return true;
    return chars[from] != chars[to] ? false 
                                    : isPalindrome(chars, from + 1, to - 1);
}

public static boolean isPalindrome(final String s) {
    return isPalindrome(s.toCharArray(), 0, s.length() - 1);
}

    Die Idee ist, dass wir verfolgen zwei Positionen im array, eine am Anfang und eine andere am Ende, und wir halten das verschieben der Positionen in Richtung der Mitte.

    Wenn die Positionen überlappen, und übergeben wir fertig sind, vergleichen Sie alle Zeichen und alle Zeichen so weit angepasst haben; die Zeichenfolge ist Palindrom.

    In jedem Durchlauf vergleichen wir die Charaktere-und wenn Sie nicht übereinstimmt, dann wird die Zeichenfolge nicht Palindrom-sonst verschieben sich die Positionen näher.

    Deine Lösung ist elegant, aber ich fürchte, es ist zu stumpf für einen Anfänger zu verstehen, intuitiv. Vielleicht fügen Sie einige Kommentare?
    sicher, lassen Sie mich zu erweitern, dass ein wenig.
    +1 für eine tolle Erklärung und slick-code!

    InformationsquelleAutor Marimuthu Madasamy

  3. 5

    Es ist eigentlich ausreichend, um nur zu überprüfen, bis zu der Mitte-Zeichen, um zu bestätigen, dass es ein Palindrom, was bedeutet, Sie vereinfachen es, bis auf so etwas wie dieses:

    //Length of my string.
int length = myString.length();

//Loop over first half of string and match with opposite character.
for (int i = 0; i <= length / 2; i++) {
    //If we find one that doesn't match then return false.
    if (myString.charAt(i) != myString.charAt(length - 1 - i)) return false;
}

//They all match, so we have found a palindrome!
return true;

    Einer rekursiven Lösung ist sehr gut möglich, aber es wird nicht geben Sie jede Leistung (und wahrscheinlich nicht so gut lesbar).

    Ich verstehe nicht. Würde man nicht prüfen müssen, ob die zweite Hälfte des Wortes??? Wie kann die überprüfung bis zu mittleren Charakter garantieren, es ist ein Palindrom?
    Da Sie bereits überprüft die zweite Hälfte, Wenn Sie den ersten Charakter, vergleichen Sie es, um die Letzte, wenn Sie vergleichen die 2. Charakter, vergleichen Sie es, um die 2 letzten. Wenn Sie in der Mitte alle Buchstaben verglichen worden.
    natürlich 🙂 macht voll Sinn, jetzt, danke!

    InformationsquelleAutor Joe F

  4. 1

    Kann dies umgesetzt werden Rekursiv?

    JA

    Hier ist ein Beispiel:

    public static boolean palindrome(String str)
{
    if (str.length()==1 || str.length == 0)
    return true;
    char c1 = str.charAt(0);
    char c2 = str.charAt(str.length() - 1);
    if (str.length() == 2)
    {
        if (c1 == c2)
        return true;
        else
        return false;
    }
    if (c1 == c2)
    return palindrome(str.substring(1,str.length() - 1));
    else
    return false;
}
    können Sie mir sagen, diese Worte neben den 0 Länge Wort, wo es scheitert?
    also heißt es, außer für 0 Länge Wort, es ist in Ordnung, für alle anderen Worte..richtig?

    InformationsquelleAutor Vishal K

  5. 1

    Meine zwei Cent. Es ist immer schön zu sehen die verschiedenen Möglichkeiten, die Menschen lösen ein problem. Natürlich ist dies nicht der effizienteste Algorithmus, der Speicher oder die Geschwindigkeit klug.

    public static boolean isPalindrome(String s) {

    if (s.length() <= 1) { //got to the middle, no need for more checks
        return true;
    }

    char l = s.charAt(0); //first char
    char r = s.charAt(s.length() - 1); //last char

    if (l == r) { //same char? keep checking
        String sub = s.substring(1, s.length() - 1);
        return isPalindrome(sub);
    }

    return false;
}

    InformationsquelleAutor Hlodowig

Schreibe einen Kommentar