[Leet Code] 125. Valid Palindrome

提问链接

問題の説明

A phrase is a palindrome if, after converting all uppercase letters into lowercase letters and removing all non-alphanumeric characters, it reads the same forward and backward. Alphanumeric characters include letters and numbers.
Given a string s, return true if it is a palindrome, or false otherwise.

例

Input: s = "A man, a plan, a canal: Panama"
Output: true
Explanation: "amanaplanacanalpanama"is a palindrome.

制限

1 <= s.length <= 2 * 10^5
s consists only of printable ASCII characters.

私の答え

フェリンドロムは反意語だ.
大文字と小文字を区別しないため、小文字に変換してリストを作成し、文字列の各文字を1つずつ抽出してリストに入れます.
グライダーで反転し、フィリンドロムならTrueに戻ります.
test cases passedRuntimeMemory Usage480/48062 ms15.8 MB

class Solution:
    def isPalindrome(self, s: str) -> bool:
        s = s.lower()
        s_list = []
        for i in s:
            if i.isalnum():
                s_list.append(i)
        if s_list == s_list[::-1]:
            return True
        return False

プール1:リストに変換

ここの興味深い部分は、フェリンドロンを見分けたとき、
pop()を使用して、リストの一番前の値と一番後ろの値を比較します.
test cases passedRuntimeMemory Usage480/480236 ms19.6 MB

class Solution:
    def isPalindrome(self, s: str) -> bool:
        s = s.lower()
        strs = []
        for c in s:
            if c.isalnum():
                strs.append(c.lower())
        while len(strs)> 1:
            if strs.pop(0) != strs.pop():
                return False
        return True

プール2:Darkの使用

プール1のリストをdeckとして使用すると、速度が向上します.
リスト中のpop(0)はO(N)であり、Deck中のpopleft()はO(1)であるため、約5倍の速度を向上させることができる.
繰り返しN回ごとにリストがO(N^2)、パケットがO(N)となるため性能に差がある.
test cases passedRuntimeMemory Usage480/48057 ms19.6 MB

from collections import deque
class Solution:
    def isPalindrome(self, s: str) -> bool:
        s = s.lower()
        strs = deque()
        for c in s:
            if c.isalnum():
                strs.append(c.lower())
        while len(strs)> 1:
            if strs.popleft() != strs.pop():
                return False
        return True

プール3:スライド

正規表現とスライドを使用しました.
スレイシンは内部でC言語を採用しているので,前の解答よりも速い性能が期待できる.
ペーストは2より1.5倍ほど速いです.
test cases passedRuntimeMemory Usage480/48040 ms15.7 MB

import re
class Solution:
    def isPalindrome(self, s: str) -> bool:
        s = s.lower()
        s = re.sub('[^a-z0-9]', '', s)
        return s == s[::-1]