いいものをつくろう

CTOの日記

アルゴリズム

【アルゴリズム脳トレ】leetcode easy 125 valid palindrom

投稿日:

こんにちは

今回の学びは

alphanumeric charactersは英数字という意味です

まずは入出力をしっかりおさえましょう

 

問題は。。。

(時間配分は5分問題理解 10分検討 10分実装  20分振り返り の一文45分構成)

まずは入出力をしっかりおさえましょう。

 

今回もつまづいたの(7分のロス)で大事なのでもう一度いいます

まずは入出力をしっかりおさえましょう。

 

実装はすぐにできたけど、このケースで引っかかってしまった。ハテと。
("OP", False),
("0P", False), # this is very hard to see

問題文のこれ、alphanumeric characters
英数字という意味で
数字もふくみます!!!がびーん

 

alphanumeric charactersは英数字という意味です

実装前後でこれは毎回書きましょう。timespace analysis (時間とスペースの分析)は o(n)

実際の実装はこちら

class Solution:
    def isPalindrome(self, s: str) -> bool:
        # l, r point
        # ignore non-alphabet
        # case insensitive
        length = len(s)
        if s == None: return False
        if s == "": return True

        l = 0
        r = length-1

        while l <= r:
            if not (s[l].isalpha() or s[l].isnumeric()) : l+=1; continue;
            if not (s[r].isalpha() or s[r].isnumeric()): r-=1; continue;
            if s[l].lower() != s[r].lower(): return False
            l += 1
            r -= 1
        return True

 

実装後です。timespace analysis (時間とスペースの分析)は o(n)

 

まとめ

alphanumeric charactersは英数字という意味です

まずは入出力をしっかりおさえましょう

 

以上です

-アルゴリズム

Copyright© CTOの日記 , 2020 All Rights Reserved.