[PYTHON] Lassen Sie Code Day51 "647. Palindromic Substrings" ab Null

Überblick

Es scheint, dass Codierungstests in Ingenieurinterviews im Ausland durchgeführt werden, und in vielen Fällen besteht die Hauptsache darin, bestimmte Funktionen und Klassen entsprechend dem Thema zu implementieren.

Als Gegenmaßnahme scheint eine Website namens Let Code Maßnahmen zu ergreifen.

Eine Site, die algorithmische Leistung trainiert, die Codierungstests standhält, über die früh gesprochen wird.

Ich denke, es ist besser, die Algorithmuskraft eines Menschen zu haben, also werde ich das Problem unregelmäßig lösen und die Methode, die ich damals dachte, als Memo aufschreiben.

Leetcode

Leet Code-Tabelle ab Null

Letztes Mal Leet Code Day 50 "739. Tägliche Temperaturen" ab Null

Im Moment priorisiere ich das Medium der 100 beliebtesten Fragen. Easy wurde gelöst. Wenn Sie interessiert sind, gehen Sie bitte zum Tisch.

Twitter Ich mache es.

Problem

647. Palindromic Substrings Der Schwierigkeitsgrad ist Mittel. Auszug aus den 100 beliebtesten Fragen.

Das Problem ist, dass die Zeichenfolge s angegeben ist. Implementieren Sie einen Algorithmus, der die Anzahl der Zyklen in dieser Zeichenfolge zählt und diese Anzahl zurückgibt.

Teilzeichenfolgen mit unterschiedlichen Start- oder Endindizes werden als unterschiedliche Teilzeichenfolgen gezählt, auch wenn sie aus denselben Zeichen bestehen.

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".

Lösung

Als übliche Methode zum Überprüfen eines Satzes bedeutet dies, dass es sich um einen Satz handelt, wenn derjenige, der die Zeichenfolge von Anfang an geleckt hat, und derjenige, der von der gegenüberliegenden Übereinstimmung geleckt hat, übereinstimmen.

Wenn Bruteforce (Round-Robin) in Ordnung ist, können Sie die for-Anweisung verdoppeln. Wenn Sie jedoch die for-Anweisung verdoppeln, beträgt der Berechnungsbetrag O (N ^ 2), was sehr langsam ist. Ich werde.

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.

Schauen wir uns die Diskussion an, um zu sehen, welche anderen Lösungen verfügbar sind. Zum Beispiel [diese Lösung](https://leetcode.com/problems/palindromic-substrings/discuss/392119/Solution-in-Python-3-(beats-~94)-(six-lines)-(With- Detaiiled-Erklärung)).

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.		

Der konditionierende Teil der while-Anweisung ist der Schlüssel. Ich fand es erstaunlich, ohne solche Auslassungen und Überschneidungen fest über den Fluss nachdenken zu können.

Es ist auf den ersten Blick leicht zu verstehen und obwohl es auf Englisch ist, wird es ausführlich erklärt. Wenn Sie also interessiert sind, können Sie es unter dem Link überprüfen.

Das ist alles für heute. Danke für deine harte Arbeit.