Une autre façon de vérifier les palindromes

Ces jours-ci, je parcourais Linkedin et Twitter et j'ai vu un défi de codage très courant : vérifier si une chaîne est un palindrome.

C'est un défi très simple. Un palindrome est un mot ou une phrase qui peut être lu de la même manière vers l’intérieur et vers l’arrière. Comme :

• tesset
• maman
• biaib

et ainsi de suite.

Mais l'approche générale que les gens suivent est la suivante :

En d'autres termes, ils prennent la chaîne d'origine puis l'inversent, puis la comparent à l'original.
C'est une approche très valable, mais je souhaite suggérer une approche intelligente.

Voyez que vous devez produire une nouvelle allocation pour la chaîne, puis comparez caractère par caractère. La façon dont cela peut être plus difficile est de savoir comment le faire en utilisant un O(1) plus de mémoire et en faisant moins de comparaisons ?

Laissez-moi mieux expliquer cela.

La meilleure approche pour résoudre ce problème consiste à utiliser une approche à deux points.

Une chaîne n'est rien de plus qu'un tableau de caractères, et nous pouvons la parcourir char par caractère, et faire des parcours et des comparaisons avec n'importe quel caractère du tableau.

Refactorisons-le en utilisant la nouvelle approche utilisant deux pointeurs.
La première chose que nous devons faire est d'en prendre une tranche de rune :

  r := []rune(str);

Les chaînes dans Go sont en lecture seule, donc fondamentalement, la chaîne est immuable et ne peut pas être modifiée. La tranche de rune, sinon, peut être modifiée, puis la conversion entre les deux fait une copie des octets de la chaîne, mais nous ne faisons pas une autre copie ici, car nous continuerons dans le même cadre de pile, et nous ne le faisons pas. je vais produire une nouvelle chaîne.

Après cela, on va commencer la boucle, avec un pointeur au début de la rune et un autre à la fin, et on va la parcourir jusqu'à ce que l'un en croise un autre. Nous allons faire les comparaisons ici :

func isPalindrome(str string) bool {
    r := []rune(str)
    for i, j := 0, len(r)-1; i < j; i, j = i+1, j-1 {
        if r[i] != r[j] {
            return false
        }
    }
    return true
}

De cette façon, si les comparaisons se passent bien et que tous les caractères sont identiques, alors c'est un palindrome. Sinon, il renvoie false instantanément.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!