LeetCode 125. Valid Palindrome (Python3)
はじめに
LeetCode 「125. Valid Palindrome」の問題を Python3 で解きました。
問題
問題文
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.
和訳
ある語句が回文であるとは、大文字をすべて小文字に変換し、英数字以外の文字をすべて除去した後、前後どちらから読んでも同じになることを指す。英数字には文字と数字が含まれる。
与えられた文字列 s が回文である場合 true を返し、そうでない場合は false を返す。
例
Input: s = "A man, a plan, a canal: Panama"
Output: true
Explanation: "amanaplanacanalpanama" is a palindrome.
Input: s = "race a car"
Output: false
Explanation: "raceacar" is not a palindrome.
Input: s = " "
Output: true
Explanation: s is an empty string "" after removing non-alphanumeric characters.
Since an empty string reads the same forward and backward, it is a palindrome.
制約
- 1 <= s.length <= 2 * 105
- s consists only of printable ASCII characters.
解答1（2ポインタ）
回文かどうかを判定するために、2ポインタのアプローチを用います。
先頭と末尾からそれぞれ文字を比較しながら中央に向かって進んでいくことで判定することが可能です。
文字列から英数字以外の文字を除去する必要がありますが、正規表現を使い以下のように処理することが可能です。
s = re.sub(r"[^a-z0-9]", "", s.lower())
なお、以下のような書き方も可能です。
s = "".join(ch.lower() for ch in s if ch.isalnum())
s = [ch.lower() for ch in s if ch.isalnum()]
コード
class Solution:
def isPalindrome(self, s: str) -> bool:
s = re.sub(r"[^a-z0-9]", "", s.lower())
left = 0
right = len(s) - 1
while left < right:
if s[left] != s[right]:
return False
else:
left += 1
right -= 1
return True
計算量
- 時間的計算量：O(n)
- 空間的計算量：O(n)
解答2（スライス操作で逆順）
スライス操作を使用することでよりシンプルに解くことができます。
スライスは以下のようにステップを指定することが可能です。
sequence[start:stop:step]
ステップに負数を指定することで、マイナス方向に向かって切り取りが行われます。
シーケンスをリバースする簡潔な方法として使用されます。
s[::-1]
コード
class Solution:
def isPalindrome(self, s: str) -> bool:
s = re.sub(r"[^a-z0-9]", "", s.lower())
return s == s[::-1]
計算量
- 時間的計算量：O(n)
- 空間的計算量：O(n)
Discussion