É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

  1. Avoir 2 boucles for

    pour i = 1 à i moins de tableau.longueur -1

    pour j=i+1 à j moins de tableau.longueur
  2. De cette façon, vous pouvez obtenir des sous-chaîne de toutes les combinaisons possibles à partir du tableau
  3. Ont un palindrome fonction qui vérifie si une chaîne est palindrome
  4. ainsi, pour chaque substring (i,j) appel de cette fonction, si c'est un palindrome de le stocker dans une variable de chaîne
  5. 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.
  6. Enfin votre variable de chaîne aurez la réponse

Questions:
1. Cette algo s'exécute en O(n^2).

Algo 2:

  1. D'inverser la chaîne et de le stocker dans diferent tableau
  2. Maintenant trouver le plus grand sous-chaîne correspondante entre le tableau
  3. 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 de O(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

InformationsquelleAutor Learner | 2009-07-12