Leetcode 125. Valid Palindrome

Problem

この問題は、与えられた文字列が回文（前から読んでも後ろから読んでも同じになる文字列）かどうかを判断するというものです。

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.

InputとOutputの例です。

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

Key Idea

2つのアイデアがあります。
1つ目のアイデアは、回分ならば文字列を逆にしても同じ文字列となるはず、というものです。
2つ目のアイデアは、2つポインタを使って、左からと右から一要素ずつ比較していく、というものです。

Alphanumeric characters

この問題は、回分判定の前段階として、文字中の英数字のみを考慮します。これには、Pythonでは、ビルトインのisalnum()関数を使う方法と、正規表現を使う方法があります。
正規表現では、re.sub(r'[^a-z0-9]', '', s)と書くことができます。a-zもしくは0-9にマッチしない文字(^)の置換を行います。
Leetcodeの他の方の回答を見た印象では、s.isalnum()関数を使う方が一般的なのかもしれません。

Approach #1 Compare with Reverse

最初に、非英数字の文字を取り除き、すべて小文字に変換します。その後、文字列がその逆順と等しければ、それは回文であると判定します。リストの逆順は、list[::-1]で表現できます。

class Solution:
    def isPalindrome(self, s: str) -> bool:

        new_str = ''
        for c in s.lower():
            if c.isalnum():
                new_str = new_str + c

        # One linerでこのように書くことも可能です
        # new_str = ''.join(c for c in s if c.isalnum()).lower()

        reversed_str = new_str[::-1]
        return new_str == reversed_str

この解法では、計算量は下記の様になります。

• Time complexity: O(n)。1)lower関数、2)文字列の変換、3) 文字列の逆順化 4) 2つの文字列の比較のそれぞれがO(n)の時間を必要とします。ここで、nは文字列の長さです。

• Space complexity: O(n)。1)lower関数、2)文字列の変換、3) 文字列の逆順化 のそれぞれでO(n)のメモリを必要とします。文字列の比較には追加のメモリは必要ないため、O(1)です。

Approach #2 Two Pointers

2つのポインタ（一つは先頭から、もう一つは末尾から）を使用して文字列をスキャンし、各ステップでポインタが指す文字が等しいか確認することができます。この場合メモリ使用量を削減することができます。

class Solution:
    def isPalindrome(self, s: str) -> bool:

        left, right = 0, len(s) - 1

        print(s)
        while left < right:
            while (left < right) and (not s[left].isalnum()):
                left += 1

            while (left < right) and (not s[right].isalnum()):
                right -= 1

            if s[left].lower() != s[right].lower():
                return False
            left, right = left + 1, right - 1

        return True

while (left < right) and (not s[left].isalnum()) で left < rightの条件を忘れないようにする必要があります。文字列の左右からスキャンしている際に、左のポインタが右のポインタを追い越さないようにするためです。ここで left < rightの条件を忘れると、ポインタが文字列の範囲外に移動しエラーが発生する可能性があります。これは、与えられた文字列のすべてが非英数字の文字で構成されている場合などに発生します。このエラーを防ぎ、両ポインタが適切な範囲内に留まることを確保します。

この解法では、計算量は下記の様になります。

• Time complexity: O(n)。1) 非英数字のスキッピングと while (left < right) and (not s[left].isalnum()) のそれぞれがO(n)の時間を必要とします。ここで、nは文字列の長さです。

• Space complexity: O(1)。Approach #2では、文字列の変換も文字列の逆順化もおこなっていません。また、文字列の比較やlower関数の利用もも1文字１文字実施しています。

Reference