Écrire une fonction qui retourne le plus long palindrome dans une chaîne
e.g "ccddcc" dans la chaîne "abaccddccefe"
J'ai pensé à une solution, mais il s'exécute en O(n^2)
Algo 1:
Suit:
Sa force brute méthode
- Avoir 2 boucles for
pour i = 1 à i moins de tableau.longueur -1
pour j=i+1 à j moins de tableau.longueur - De cette façon, vous pouvez obtenir des sous-chaîne de toutes les combinaisons possibles à partir du tableau
- Ont un palindrome fonction qui vérifie si une chaîne est palindrome
- ainsi, pour chaque substring (i,j) appel de cette fonction, si c'est un palindrome de le stocker dans une variable de chaîne
- Si vous trouvez à côté palindrome sous-chaîne et si il est plus grand que l'actuel, de le remplacer avec de l'actuel.
- Enfin votre variable de chaîne aurez la réponse
Questions:
1. Cette algo s'exécute en O(n^2).
Algo 2:
- D'inverser la chaîne et de le stocker dans diferent tableau
- Maintenant trouver le plus grand sous-chaîne correspondante entre le tableau
- Mais cela aussi s'exécute en O(n^2)
Pouvez-vous les gars pensez à un algo qui s'exécute dans un temps meilleur. Si possible O(n) le temps
- Je pense que le premier est
O(n^2)
pour obtenir les sous-chaînes *O(n)
pour vérifier si elles sont des palindromes, pour un total deO(n^3)
? - Que faire si je savais que je travaillais avec palindrome et enregistrer mes chaînes comme deux moitiés, et puis si j'ai utilisé Java j'aurais O(1) case pour la fonction?
- Le secong algo est correcte? Que penser de la chaîne: "abcdecba". Le plus grand sous-chaîne correspondante est ("abcdecba" vs "abcedcba"): "abc" ou "abc". Toutefois, les deux ne sont pas des palindromes.
- juste curieux, à vous les étapes au-dessus de ce tableau sont vous de l'arbitrage dans le cadre de votre boucles for? Par tableau êtes-vous référant à la chaîne? chaîne de caractères.longueur?
- voir dans l'une des réponses ci-dessous, le wiki: en.wikipedia.org/wiki/Longest_palindromic_substring
- c'est compliqué, et la chose principale est que trop est de O(n^2)- lors de la boucle à l'intérieur de la boucle
- pour ceux à la recherche de réponse à O(n^2) - geeksforgeeks.org/longest-palindrome-substring-set-1
Vous devez vous connecter pour publier un commentaire.
Vous pouvez trouver le plus long palindrome de l'aide Manacher de l'Algorithme de dans
O(n)
temps! Sa mise en œuvre peut être trouvé ici et ici.Pour l'entrée
String s = "HYTBCABADEFGHABCDEDCBAGHTFYW1234567887654321ZWETYGDE"
il trouve la bonne sortie qui est1234567887654321
.while
incorporé dans lefor
avec un cadre qui semble similaire à la boucle externe.L'Algo 2 peut ne pas fonctionner pour toutes les chaînes de caractères. Voici un exemple d'une telle chaîne "ABCDEFCBA".
Pas que la chaîne "ABC" et "ABC", comme son sous-chaîne. Si vous inversez la chaîne d'origine, il sera "ABCFEDCBA". et de la plus longue sous-chaîne correspondante est "ABC", qui n'est pas un palindrome.
Vous pouvez avoir besoin de vérifier si cette plus longue sous-chaîne correspondante est en fait un palindrome qui a le temps d'exécution de O(n^3).
Que j'ai compris le problème, nous pouvons trouver des palindromes autour d'un centre d'index et de la durée de notre recherche dans les deux sens, à droite et à gauche du centre. Étant donné que savoir il n'y a pas de palindrome sur les coins de l'entrée, nous pouvons définir les limites de 1 et de longueur-1. Tout en accordant une attention à la le minimum et le maximum des limites de la Chaîne, nous vérifions si les caractères à la position de la symétrie des index (droite et gauche) sont les mêmes pour chaque position centrale jusqu'à ce que nous atteignons notre max la limite supérieure de centre.
La boucle externe est O(n) (max n-2 itérations), l'intérieur de la boucle while est O(n) (max autour de (n /2) - 1 itérations)
Voici mon Java mise en œuvre à l'aide de l'exemple fourni par d'autres utilisateurs.
La sortie de cette est la suivante:
expandAroundCenter
.avec la regex et ruby, vous pouvez numériser pour de courtes palindromes comme ceci:
J'étais posé cette question récemment. Voici la solution que j'ai [finalement] est venu avec. Je l'ai fait en JavaScript car c'est assez simple dans cette langue.
Le concept de base est que vous marchez la chaîne à la recherche pour les plus petits caractères multi-palindrome possible (l'une des deux ou trois caractères (un). Une fois que vous avez cela, élargir les frontières des deux côtés jusqu'à ce qu'il cesse d'être un palindrome. Si cette durée est plus longue que la plus longue, de les stocker et de les déplacer le long.
Cela pourrait certainement être nettoyé et optimisé un peu plus, mais il devrait avoir assez de bonnes performances dans tous mais le pire scénario (une chaîne de la même lettre).
i
j
l
s
if
et de l'état d'entretien. multi les points de retour, les cas de bord...Salut Voici mon code pour trouver le plus long palindrome de la chaîne.
Merci de consulter le lien suivant pour comprendre l'algorithme http://stevekrenzel.com/articles/longest-palnidrome
Des données de Test utilisé est HYTBCABADEFGHABCDEDCBAGHTFYW12345678987654321ZWETYGDE
Voir Article de Wikipedia sur ce sujet. Exemple de Manacher de l'Algorithme de Java application linéaire O(n), solution à partir de l'article ci-dessous:
Efficace
Regexp
solution qui évite la force bruteCommence avec toute la longueur de la chaîne et travaille à la baisse à 2 caractères, existe dès qu'une correspondance est faite
Pour
"abaccddccefe"
la regexp tests 7 matches avant de retournerccddcc
.vbs
vba
fonction
J'ai écrit un programme en Java par curiosité, simple et auto-explicative HTH. Merci.
Essayer à la chaîne "HYTBCABADEFGHABCDEDCBAGHTFYW123456789987654321ZWETYGDE";
Il doit travailler de pair et de l'impair de l'epla. Merci beaucoup à Mohit!
using namespace std;
isPal
-- un O(n) opération -- seulement de mesurer sa longueur!? Il a également un buggy tentative de manipulation de même des palindromes. Sur le même-palindrome bugginess:else if(input_str[i] == input_str[j])
ne peut jamais réussir parce que même test doit avoir échoué dans le précédentif
de la déclaration; et il le buggy de toute façon parce que vous ne pouvez pas dire tout simplement en regardant les 2 caractères espacés de 2 postes à part si vous êtes à la recherche à un palindrome ou un étrange (pensez àAAA
etAAAA
).Code suivant calcule Palidrom de même longueur et de l'impair de la longueur des chaînes.
Pas la meilleure solution, mais travaille pour les deux cas
HYTBCABADEFGHABCDEDCBAGHTFYW12345678987654321ZWETYGDE
HYTBCABADEFGHABCDEDCBAGHTFYW1234567887654321ZWETYGDE
Nous pouvons trouver tous les palindromes de toute la longueur à l'aide de ce.
Exemple :
mot = abcdcbc
modifiedString = a#b#c#d#c#b#c
palinCount = 1010105010301
longueur du plus long palindrome = 5;
plus long palindrome = bcdcb
public class MyLongestPalindrome {
}
Ce sera de retour le plus long palindrome de la chaîne d'une chaîne donnée
== OUTPUT ===
D'entrée: abcccde de Sortie: ccc
D'entrée: abcccbd de Sortie: bcccb
D'entrée: abedccde de Sortie: edccde
D'entrée: abcccdeed de Sortie: acte
D'entrée: abcccbadeed de Sortie: abcccba
Voici une implémentation en javascript:
JS:
Linéaire de la solution, vous pouvez utiliser Manacher de l'algorithme. Il existe un autre algorithme d'appel Gusfield de l'Algorithme, et ci-dessous est le code en java:
Vous pouvez en savoir plus sur d'autres solutions comme le meilleur O(n^2) solution ou Manacher de l'algorithme de mon propre blog.
Ici, j'ai écrit une logique d'essayer 🙂
Cette Solution est de O(n^2) complexité. O(1) est l'espace de la complexité.
HTML:
{'DED': 3, '123456789987654321': 18, '67899876': 8, 'ABCDEDCBA': 9, '456789987654': 12, '34567899876543': 14, 'BCDEDCB': 7, "ABA': 3, '5678998765': 10, '2345678998765432': 16, 'CDEDC': 5, '789987': 6, '8998': 4}
('123456789987654321', 18)
Voici mon algorithme:
1) définir le centre de la première lettre
2) simultanément étendre à droite et à gauche jusqu'à ce que vous trouver le maximum de palindrome autour de l'actuel centre
3) si le palindrome vous trouver est plus grand que le précédent palindrome, mise à jour, il
4) définir le centre de la lettre suivante
5) répétez l'étape 2) à 4) pour toutes les lettres de la chaîne
Cela s'exécute en O(n).
Espère que cela aide.
De Référence: Wikipedia.com
Le meilleur algorithme que j'ai jamais trouvé, avec une complexité O(N)
ma solution est la suivante :
Substring()
et de la chaîne de l'égalité (==
) opérations. C'est essentiellement identique à l'opération de l'algo #1.