Palindrome

[kulturfenster]

zur Begriffserklärung: http://de.wikipedia.org/wiki/Palindrom

Ich habe eine Methode geschrieben, die testen soll, ob es sich um ein Palindrome handelt oder nicht. Leider bekomme ich immer eine "false" ausgabe, obwohl ich nicht verstehe wieso.

Zuerst testet die Methode, ob die Länge des String kleiner gleich 1 ist und gibt, falls ja, true zurück. Ansonsten wird gestestet, ob der 1. und der letzte Buchstabe gleich sind. Falls ja, wie die Methode rekursiv aufgerufen mit einem String ohne Anfangs- und Endbuchstabe.

Könnte kurz jemand einen Blick drauf werfen und mir andeuten, wo ich einen Fehler gemacht habe? Oder wie ich herausfinden kann, wo der Fehler liegt?

Vielen Dank!

public class Palindrome {

	public boolean isPalindrome(String text)
	{
		if(text.length() <= 1) return true;
		if(text.substring(0, 1).equalsIgnoreCase(text.substring(text.length()-1, text.length() )))
		{
                        // zu testzwecken...
			System.out.println(text.substring(1,text.length()-1));
			isPalindrome(text.substring(1,text.length()-1));
			
		}
			
		return false;
	}
	
	public static void main(String[] args)
	{
		Palindrome p = new Palindrome();
		System.out.println(p.isPalindrome("rentner"));
	}
}

 

[SlaterB]

dein Programm spricht doch mit dir...

public class Test2
{

    public boolean isPalindrome(String text)
    {
        if (text.length() <= 1)
        {
            System.out.println("isPal: text.length < 1 -> true");
            return true;
        }
        if (text.substring(0, 1).equalsIgnoreCase(text.substring(text.length() - 1, text.length())))
        {

            System.out.println(text.substring(1, text.length() - 1));
            isPalindrome(text.substring(1, text.length() - 1));

        }
        System.out.println("isPal: egal was sonst so los ist, ich gebe zurück: false");
        return false;
    }

    public static void main(String[] args)
    {
        Test2 p = new Test2();
        System.out.println(p.isPalindrome("rentner"));
    }

 

[The_S]

Rekursive aufrufe sind sehr Speicherlastig. Wenn es geht lieber Schleifen verwenden. Vorschlag: Eine Schleife mit zwei Zeigern. Einer auf dem ersten Element, einer auf dem letzten. Wenn beide Zeichen identisch sind, geht der erste Zeiger ein Zeichen weiter und der letzte ein Zeichen zurück. Treffen sich beide, gibst du true zurück. Sind die Zeichen irgendwann nicht identisch, gibst du false zurück!

 

[Guest]

Das Problem ist, daß nur der letzte Rekursionsaufruf true zurückliefert, Du dieses Ergebnis aber nicht auswertest und immer false zurückgibst.

 

[kulturfenster]

hab ich das richtig verstanden, dass vor jedem rekursiven Aufruf die Methode per return beendet werden muss?

dh.

return isPalindrome(text.substring(1,text.length()-1));

@Hobbit:

Vielen Dank für den Tipp. In der Aufgabe geht es um Rekursion, trotzdem werde ich deinen Hinweis gleich versuchen umzusetzen...

 

[SlaterB]

> dass vor jedem rekursiven Aufruf die Methode per return beendet werden muss

'vor' trifft es nicht wirklich,
du führst die Rekursion aus und bist dann fertig,
aber der Code sollte dann stimmen, ja (testen!)

 

[The_S]

Vielen Dank für den Tipp. In der Aufgabe geht es um Rekursion, trotzdem werde ich deinen Hinweis gleich versuchen umzusetzen...

Achso, wenn es sich um eine Aufgabe handelt und dort gefordert ist rekursion zu verwenden, kannst du meine Methode natürlich vergessen .

 

[Guest]

Achso, wenn es sich um eine Aufgabe handelt und dort gefordert ist rekursion zu verwenden, kannst du meine Methode natürlich vergessen .

Interessant ist es trotzdem!

public static boolean istPalindrom(String wort)
{
	wort = wort.toLowerCase();
	int vorne = 0;
	int hinten = wort.length() - 1;
	while (vorne < hinten && wort.charAt(vorne) == wort.charAt(hinten))
	{
		++vorne;
		--hinten;
	}
	return vorne >= hinten;
}

public static void teste(String wort)
{
	System.out.printf("\"%s\" ist %sein Palindrom\n", wort, istPalindrom(wort) ? "" : "k");
}

public static void main(String[] args)
{
	teste("rentner");
	teste("haus");
	teste("Regal-Lager");
	teste("X");
	teste("");
}

"rentner" ist ein Palindrom
"haus" ist kein Palindrom
"Regal-Lager" ist ein Palindrom
"X" ist ein Palindrom
"" ist ein Palindrom

Fred

 

[Marco13]

Man kann das auch rekursiv machen, OHNE bei jedem Aufruf einen neuen substring zu machen. Stattdessen kann man die zu überprüfenen indizes mitgeben

prüfe(string, 0, 5);
    prüfe(string, 1, 4);
       prüfe(string, 2, 3);
           prüfe(string, 3, 2); Ende

 

[The_S]

@Gast

Naja, gewisse Feinheiten müssen halt noch zusätzlich berücksichtigt werden (z. B. die minimale Wortlänge), und ansich könnte man das auch so leicht rekursiv umschreiben

 

[kulturfenster]

Vielen Dank für die rege Beteiligung!

noch ein paar Fragen:

Ich hab die iterative Version etwas anders gemacht:

if(text.charAt(i) == text.charAt(j))
			{
				if(j-i <= 1) return true;
			}

wieso verlangt die charAt-Methode einen "==" - Vergleich anstelle von equals? Ich dachte, wenn mit Strings hantiert wird, handelt es sich nie um primitive Datentypen?

System.out.printf("\"%s\" ist %sein Palindrom\n", wort, istPalindrom(wort) ? "" : "k");

Kann man irgendwo nachlesen, was diese hieroglyphen bedeuten?

 

[The_S]

Wenn du Objetke verlgeichst => equals. Wenn du primitive Datentypen vergleichst => == . Wie du jetzt darauf kommst ein char einem String gleichzusetzen will mir nicht ganz einleuchten ???:L

 

[ARadauer]

in zeile 10 fehlt das return

 

[Guest]

wieso verlangt die charAt-Methode einen "==" - Vergleich anstelle von equals?

Die charAt-Methode liefert einen char zurück. Das ist ein primitiver Werttyp, der ganz normal mit == verglichen wird.

System.out.printf("\"%s\" ist %sein Palindrom\n", wort, istPalindrom(wort) ? "" : "k");

Kann man irgendwo nachlesen, was diese hieroglyphen bedeuten?

Dann wollen wir das mal zerpflücken

istPalindrom(wort) ? "" : "k"

Was Du hier siehst, ist der ternäre Operator ?: welcher als einziger 3 Operanden besitzt. Allgemein sieht er so aus:

boolexp ? exptrue : expfalse

Die Bedeutung davon ist: Werte den bool'schen Ausdruck boolexp aus. Falls das Ergebnis true ist, dann ist das Gesamtergebnis das Ergebnis der Auswertung von exptrue, andernfalls von expfalse.

In unserem speziellen Fall heisst das also: schau nach, ob das Wort ein Palindrom ja ist. Falls ja, liefere den leeren String, ansonsten den String "k".

Das erste Argument von printf ist ein sogenannter Format-String. Dieser wird im Prinzip ganz normal weitergegeben, bis auf die Stellen, die mit einm %-Zeichen beginnen. %s bedeutet, dass an dieser Stelle ein String eingefügt werden soll. Welcher, das steht in den anderen Parametern von printf. Hier ist es wort.

%sein musst Du als zwei Dinge verstehen: %s und ein. Es wird also das Ergebnis des ternären Operators, den wir vorher schon besprochen hatten, hier eingefügt, also entweder gar nichts oder ein k. Anschliessend wird "ein" ausgegeben. ""+"ein" = "ein" und "k"+"ein" = "kein", verstehst Du?

Da ich auch Anführungsstriche ausgeben will, steht das %s zwischen \" und \". Letzteres benutzt man, wenn man in einem String-Literal einen Anführungsstrich verwenden will, was "einfach so" nicht geht, weil man ja sonst das Literal beenden würde.

Fred