🎃

NeetCode 150 [Two Pointers]:easy

2025/01/16に公開

NeetCodeのSolutionを書いていく

Valid Palindrome

回文かどうかチェック。
大文字小文字は区別しない。
アルファベット以外は比較しない。

前からと後ろからを比べれば良い。
アルファベット以外の場合は飛ばせば良い。
比較時は小文字にして比べれば良い。
前からと後ろからで配列番号を比較して、同じか逆転したら終了。

class Solution:
    def isPalindrome(self, s: str) -> bool:
        # アルファベット、数字以外を除去、小文字に揃える
        s = [c.lower() for c in s if c.isalnum()]
        length = len(s)
        for i in range(int(length/2)): # チェックは半分でいい
            fwd=i
            bwd=length-(fwd+1)
            print(s[fwd])
            print(s[bwd])
            if s[fwd] != s[bwd]:
                return False
            if fwd >= bwd:
                return True
        return True # 真ん中のチェックまで到達すれば回文

そっか、これで行けるのか!
ただ追加のメモリが必要になるわけか。

class Solution:
    def isPalindrome(self, s: str) -> bool:
        # アルファベット、数字以外を除去、小文字に揃える
        s = [c.lower() for c in s if c.isalnum()]
        return s == s[::-1]

データをコピーせずに比較するコードも回答例があるけど、バグらずに作れる自信がない!

class Solution:
    def isPalindrome(self, s: str) -> bool:
        l, r = 0, len(s) - 1

        while l < r:
            while l < r and not s[l].isalnum():
                l += 1
            while r > l and not s[r].isalnum():
                r -= 1
            if s[l].lower() != s[r].lower():
                return False
            l, r = l + 1, r - 1
        return True

Discussion