Regardez d'abord le code
classe publique maxhuiwen {public static void main (String [] args) {// TODO Méthode générée automatique Stub String S = "ABB"; Maxhuiwen (s); } // 1. Sortie palindrome String public static void maxhuiwen (chaîne s) {// stockage la longueur de la chaîne int length = s.Length (); // Stockage La chaîne de chaîne Palindrome la plus longue maxString = ""; // transize toutes les sous-chaînes de la chaîne actuelle pour (int i = 0; i <longueur; i ++) {for (int j = i; j <longueur + 1; j ++) {String s1 = s.SubString (i, j); // Si la chaîne actuelle est une chaîne Palindrome et est supérieure à la longueur de maxString, remplacez le maxString actuel if (huiwen (s1) && s1.length ()> maxString.length ()) {maxString = s1; } //System.out.println(s1); }} // Si la longueur de MaxString est supérieure ou égale à 2, cela signifie qu'il s'agit d'une chaîne palindrome if (maxString.length ()> = 2) {System.out.println (maxString); } else {System.out.println ("No Palindrome String"); }} // 2. Déterminez si la chaîne est une chaîne palindrome publique booléenne statique Huiwen (chaîne s) {booléen drapeau = true; int length = s.Length (); char s1 [] = s.tocharArray (); // avant et après, traversez la chaîne et comparez pour (int i = 0, j = longueur - 1; i <= j; i ++, j -) {if (s1 [i]! = S1 [j]) {flag = false; }} drapeau de retour; }}1. Jugement pastoral des cordes
Déterminer si une chaîne est un palindrome
Description du problème, étant donné une chaîne, comme la chaîne t = "madame"; Pour déterminer si la chaîne est un palindrome
Méthode 1: 1. Définissez deux pointeurs d'éléments de chaîne (notez que Java n'a pas le concept de pointeurs), int droit = t.Length () - 1; int Left = 0;
2. Autrement dit, la gauche commence par la gauche, la droite commence à droite et comparez si les caractères référés sont égaux en séquence. S'ils sont égaux, gauche ++, droite--; Sinon, il sera retourné directement, pas une toile de fond.
while (gauche <droit) {if (t.charat (gauche)! = t.charat (droite)) return false; gauche ++; droite -;} return true;Code:
/ * * 3: * Palindrome * Description du problème: Palindrome, anglais palindrome, fait référence à une chaîne qui lit la même chose et inversement, comme Madame, je m'aime, * Méthode 1: * Analyse: utilisez deux "pointeurs" pour scanner à partir du début et de la fin de la chaîne respectivement. Si les valeurs pointées par chaque "pointeur" sont égales, il s'agit de palindrome * / public booléen ispalindrome (chaîne s) {if (s == null) return false; int Left = 0; int droit = s.Length () - 1; while (gauche <droite) {if (s.Charat (gauche)! = S.Charat (droite)) return false; gauche ++; droite--; } return true; } Méthode 2: chaîne pastellaire telle que "madame". Si vous les inversez tous, vous obtiendrez toujours sa propre "madame". Lorsque vous comparez les deux cordes, si elles sont égales, elle est pastellaire.
1. Implémentez une fonction qui inverse les cordes
/ * * Implémentez la fonction d'inversion d'une chaîne * / private String Reverse (String str) {String strresult = ""; for (int i = str.length () - 1; i> = 0; i -) {strresult + = str.charat (i); } return strresult; } 2. Pour la chaîne cible S, d'abord, inversez-le Temp = reverse (s), puis jugez Temp.equals (s) / ** inverser la chaîne, puis la comparer avec la chaîne d'origine. S'il est égal, il est palindrome, sinon ce n'est pas * la complexité du temps de l'algorithme est o (n) * / public booléen ispalindrome2 (String s) {String temp = reverse (s); if (s.equals (temp)) return true; elsereturn false;}Deux: comment trouver la chaîne palindromique maximale pour une chaîne donnée
Par exemple, étant donné la chaîne String t = "Google", comment trouver sa plus longue sous-chaîne Palindrome "Goog"
1. L'idée la plus simple et la plus directe est de trouver toutes les sous-chaînes de la chaîne, puis de déterminer si chaque sous-chaîne est un palindrome, enregistrer, comparer et trouver le palindrome de la longueur maximale. * La complexité temporelle de l'algorithme est o (n ^ 3)
/ * * 4, trouvez la plus longue sous-chaîne de palindrome * Description du problème: Compte tenu d'une chaîne, trouvez la plus longue sous-chaîne de palindrome parmi toutes ses sous-chaînes, comme une chaîne Google, la sous-chaîne la plus longue est Goog * Analyse: * 1, la plus simple et la plus directe est: trouver toutes les sous-étages de la chaîne, puis juger si chaque sous-chaîne est une longueur de palindrome, un record, une compare La complexité est o (n ^ 3) * / public String LongestPalindrome1 (String S) {String result = null; String tempsstring = ""; // définir la longueur de la sous-chaîne Palindrome la plus longue int max = 0; // Transférer tous les éléments de la chaîne pour (int i = 0; i <s.Length (); i ++) {// Le pointeur d'indice du tableau J commence à traverser la chaîne pour (int j = s.length () - 1; j> i; j -) {// le palindrome tempmpsstring = s.substr (i, j + 1); // si Tempsstring est une sous-chaîne Palindrome et sa longueur (J-i + 1)> max if (ispalindrome (tempsstring) && (j-i + 1)> max) {max = j-i + 1; result = substring (i, j + 1); }}} Retour Résultat; }2. La deuxième idée est de juger de chaque personnage t [i] dans la chaîne
La sous-chaîne de longueur uniforme centrée sur T [i], t [i + 1] est un palindrome
Est une sous-chaîne de longueur impaire centrée sur t [i] un palindrome
String public longestpalindrome2 (String t) {String result = null; // stockage la longueur de la chaîne palindrome maximale int max = 0; // Voyagez à travers chaque caractère et jugez le sous-chaîne d'extension de parité avec chaque caractère comme centre pour (int i = 0; i <t.length (); i ++) {// définir deux pointeurs d'indice de tableau, et la séquence de la sous-séquence uniforme centrée sur i, i + 1 int pStart = i; int pend = i + 1; while (pStart> = 0 && pennd <= (t.length () - 1) && t.charat (pstart) == t.charat (pennd)) {pStart--; Pend ++; } // Si la longueur de la sous-chaîne> max, la longueur de la chaîne sous-palindrome est temporairement stockée comme la chaîne sous-palindrome la plus longue = (Pend-1) - (pstart + 1) -1 = pennd-start-1; result = substring (pStart + 1, pennd-1 + 1); } // De I en tant que centre, déterminez si la séquence impair étendue est la chaîne palindrome pstart = i-1; Pend = i + 1; while (pStart> = 0 && pennd <= (t.length () - 1) && t.charat (pstart) == t.charat (pennd)) {pStart--; Pend ++; } if (pend-Pstart-1> max) {max = pennd-Pstart-1; result = substrint (t, pstart + 1, pennd-1 + 1); }} Retour Résultat; }