🎃
NeetCode 150 [Two Pointers]:easy
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