[PYTHON] Let Code Day51 "647. Sous-chaînes palindromiques" à partir de zéro

Aperçu

Il semble que des tests de codage soient menés à l'étranger lors d'entretiens d'ingénieurs, et dans de nombreux cas, l'essentiel est d'implémenter des fonctions et des classes spécifiques en fonction du thème.

En guise de contre-mesure, il semble qu'un site appelé Let Code prendra des mesures.

Un site qui forme une puissance algorithmique capable de résister aux tests de codage dont on parle très tôt.

Je pense qu'il vaut mieux avoir la puissance de l'algorithme d'un être humain, donc je vais résoudre le problème de manière irrégulière et écrire la méthode que j'ai pensé à ce moment-là sous forme de mémo.

Leetcode

Table de codes Leet commençant à zéro

Dernière fois Leet Code Day 50 "739. Températures quotidiennes" à partir de zéro

À l'heure actuelle, je donne la priorité au moyen des 100 questions les plus appréciées. Easy a été résolu, donc si vous êtes intéressé, veuillez vous rendre à la table.

Twitter Je le fais.

problème

647. Palindromic Substrings Le niveau de difficulté est moyen. Extrait des 100 questions les plus appréciées.

Le problème est que la chaîne «s» est donnée. Implémentez un algorithme qui compte le nombre de cycles dans cette chaîne et renvoie ce nombre.

Les sous-chaînes avec des index de début ou de fin différents sont comptées comme des sous-chaînes différentes même si elles sont composées des mêmes caractères.

Input: "abc" Output: 3 Explanation: Three palindromic strings: "a", "b", "c".

Input: "aaa" Output: 6 Explanation: Six palindromic strings: "a", "a", "a", "aa", "aa", "aaa".

Solution

En tant que méthode courante de vérification d'une phrase, si celui qui a léché la chaîne de caractères depuis le début et celui qui a léché la correspondance opposée correspond, cela signifie qu'il s'agit d'une phrase.

Si Bruteforce (round-robin) convient, vous pouvez doubler l'instruction for, mais si vous doublez l'instruction for, le montant du calcul sera O (N ^ 2), ce qui sera très lent. Je vais.

class Solution:
    def countSubstrings(self, s: str) -> int:
        ans = 0
        if not s:
            return ans
        for i in range(len(s)):
            ans += 1 
            for j in range(1, i+1):
                if self.is_palindrom(s[i-j:i+1]):
                    ans += 1
        return ans

    def is_palindrom(self, s):
        return s == s[::-1]
# Runtime: 604 ms, faster than 13.54% of Python3 online submissions for Palindromic Substrings.
# Memory Usage: 13.8 MB, less than 81.86% of Python3 online submissions for Palindromic Substrings.

Jetons un coup d'œil à la discussion pour voir quelles autres solutions sont disponibles. Par exemple, [cette solution](https://leetcode.com/problems/palindromic-substrings/discuss/392119/Solution-in-Python-3-(beats-~94)-(six-lines)-(With- Explication détaillée)).

class Solution:
    def countSubstrings(self, s: str) -> int:
	    L, r = len(s), 0
	    for i in range(L):
	    	for a,b in [(i,i),(i,i+1)]:
	    		while a >= 0 and b < L and s[a] == s[b]: a -= 1; b += 1
	    		r += (b-a)//2
	    return r
# Runtime: 132 ms, faster than 71.16% of Python3 online submissions for Palindromic Substrings.
# Memory Usage: 13.8 MB, less than 71.36% of Python3 online submissions for Palindromic Substrings.		

La partie de conditionnement de l'instruction while est la clé. J'ai pensé que c'était incroyable de pouvoir penser fermement au flux sans fuir ni dupliquer comme ça.

C'est facile à comprendre à première vue, et bien qu'il soit en anglais, il explique en détail, donc si vous êtes intéressé, vous voudrez peut-être le vérifier sur le lien.

C'est tout pour aujourd'hui. Je vous remercie pour votre travail acharné.