【LeetCode】125. Valid Palindrome 解いてみた【Easy】

問題の概要

回文
アルファベットと数字以外を削除して残った文章が前から読んでも後ろから読んでも同じ文章ならTrue

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

最初に考えた解き方

・どうやってアルファベットと数字以外を削除するか
＞Unicodeに直してaからzもしくは0から9なら配列に格納？
・回文チェックは後ろから格納していくリストを上でつくったリスとから作成してリスト＝リストならTrue?
できるのか？
＞いや''.join(list)にしてから評価だな
もしくは配列は一つだけ作り、list[0] == list[-1]で評価していく？
(len(list) + 2　- 1) // 2 切り上げ回数評価

ちょっとEasyでUnicodeはないだろとカンニングしてきた

.isalnum()
という便利なのがあるようだ

何がよくなかったか？

実はUnicodeで解く方法もあった
やってみれば楽しかったのに...

解き方

絶対思いつくであろう、文を反対にする

class Solution:
    def isPalindrome(self, s: str) -> bool:
        newStr = ''
        for c in s:
            if c.isalnum():
                newStr += c.lower()
        return newStr == newStr[::-1]

左と右にポインターを作る

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

        while l < r:
            while l < r and not self.alphaNum(s[l]):
                l += 1
            while r > l and not self.alphaNum(s[r]):
                r -= 1
            if s[l].lower() != s[r].lower():
                return False
            l, r = l + 1, r - 1
        return True
    
    def alphaNum(self, c):
        return (ord('A') <= ord(c) <= ord('Z') or 
                ord('a') <= ord(c) <= ord('z') or 
                ord('0') <= ord(c) <= ord('9'))

実は左と右にというのは初期の構想と似ていた。

もしくは配列は一つだけ作り、list[0] == list[-1]で評価していく？
これである。
なんとなくstrってインデックスで参照できないのかと思って考えるのをやめてしまった
f

参考資料

おわりに

楽なほうに流れずに自分でやってみると面白くなることもある