Vérifier palindrome de manière récursive
J'ai une classe qui vérifie si une chaîne est un palindrome ou non. J'ai deux questions.
1) Est-ce le moyen le plus efficace pour vérifier palindrome?
2) cela Peut-il être mis en œuvre de manière récursive?
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;
}
}
}
Ont une classe de test pour tester cette... Doute son besoin, mais ici, c'est de toute façon si quelqu'un se soucie de l'essayer pour être en mesure de m'aider avec l'une des deux questions ci-dessus...
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");
}
}
}
merci d'avance pour toute l'aide et de l'entrée ou de l' 🙂
Vous pouvez changer ce que vous considérez être des caractères valides au moment de décider si une phrase est un palindrome. Par exemple, "Madame, monsieur, je suis Adam" est un palindrome.
donc, je devrais essayer de faire mon programme pour ignorer les caractères tels que "' "
stackoverflow.com/questions/1579977/...
Tout d'abord, filtrer tous les caractères non alphanumériques, puis vérifier qu'il soit un palindrome.
donc, je devrais essayer de faire mon programme pour ignorer les caractères tels que "' "
stackoverflow.com/questions/1579977/...
Tout d'abord, filtrer tous les caractères non alphanumériques, puis vérifier qu'il soit un palindrome.
return (word.compareTo(pal) == 0)
enregistre sur le if
.
OriginalL'auteur choloboy7 | 2013-03-30
Vous devez vous connecter pour publier un commentaire.
À mettre en œuvre un "palindrome check" de manière récursive, vous devez comparer, si les premiers et derniers caractères sont les mêmes. Si ils ne sont pas les mêmes que la chaîne est certainement pas un palindrome. Si elles sont identiques à la chaîne pourrait être un palindrome, vous devez comparer le 2ème personnage de la 2e à la dernière lettre, et ainsi de suite jusqu'à ce que vous avez strictement moins de 2 caractères restant à vérifier dans votre chaîne.
Un algorithme récursif devrait ressembler à ceci:
Remarque, que mon la récursivité méthode n'est pas plus efficace, mais
simple à comprendre
Marimuthu Madasamy a de plus efficace récursive méthode, mais est plus difficile à comprendre
qui est le meilleur approche de mise en œuvre, car il ne peut pas provoquer une un débordement de pile erreur
Je pense que tu veux dire mot.length() < 2 pour votre base de cas.
vous avez raison, merci pour repérer la faute de frappe
Mince, je pensais que je fixe,
internalPalindromeCheck
doit avoir été lecheckPalindrome
méthode.le
word.replaceAll("[^a-zA-Z0-9]","");
est une déclaration disant java pour prendre la chaîne, trouvez tous les caractères non alphanumériques, et de les remplacer par la chaîne vide. La confusion de la partie je suppose est"[^a-zA-Z0-9]"
. De ce qu'on appelle un Expression Régulière (RegEx), ils sont un outil puissant et versatile. Certainement en valeur l'apprentissage dans le temps.OriginalL'auteur recursion.ninja
Voici une autre solution récursive, mais en utilisant un tableau qui pourrait vous donner un certain avantage de performance sur la chaîne dans les appels récursifs (en évitant les
substring
oucharAt
).L'idée est que nous gardons la trace de deux positions dans le tableau, l'un au début et l'autre à la fin et nous continuons à aller de l'positions vers le centre.
Lorsque les positions de chevauchement et de passer, nous sommes fait de comparer tous les personnages et tous les caractères jusqu'à présent ont mis en correspondance; la chaîne est palindrome.
À chaque passage, nous comparons les personnages, et si elles ne correspondent pas, alors la chaîne n'est pas un palindrome sinon déplacer les positions plus proches.
bien sûr, permettez-moi de m'étendre un peu.
+1 pour une bonne explication et de la nappe de code!
OriginalL'auteur Marimuthu Madasamy
C'est effectivement suffisant de contrôler le caractère du milieu pour confirmer que c'est un palindrome, ce qui signifie que vous pouvez simplifier à quelque chose comme ceci:
Une solution récursive est très possible, mais il ne va pas vous donner un avantage en matière de performances (et n'est probablement pas aussi lisible).
Parce que vous avez déjà coché la deuxième moitié de l'année; Lorsque vous sélectionnez le premier caractère qu'on le compare à la dernière, lorsque vous comparez la 2ème caractère vous le comparez à la 2ème à la dernière. Lorsque vous atteignez le milieu de tous les personnages ont été comparés.
bien sûr 🙂 c'est plein de sens maintenant, merci!
OriginalL'auteur Joe F
OUI
Ici est un exemple:
donc, cela signifie que, sauf pour le mot de longueur 0, il fonctionne très bien pour tous les autres mots..?
OriginalL'auteur Vishal K
Mes deux cents. Il est toujours agréable de voir les différentes façons de résoudre un problème. Bien sûr, ce n'est pas le plus efficace algorithme de la mémoire ou de la vitesse sage.
OriginalL'auteur Hlodowig