【LeetCode】9. Palindrome Number　解答・解説【Python】

LeetCodeの問題を解きます。問題文は翻訳サイトと私の拙い英語力で和訳しており、正確でない可能性が高いためご注意ください。

問題文
1. 原文
2. 和訳
方針
解答
1. コメント＋コード
  1. 別解
2. コードのみ
補足・参考・感想

問題文

原文

Given an integer x, return true if x is palindrome integer.

An integer is a palindrome when it reads the same backward as forward.

For example, 121 is a palindrome while 123 is not.

和訳

整数であるxが与えられるので、回文あればTrueを返してください。

ある整数は、前から読んでも後ろから読んでも同じように読めるとき回文です。

例えば、121は回文ですが123は違います。

方針

・xを文字列型に変換し、逆順に並べ替えた後で、元のxと一致するかを調べます。

解答

コメント＋コード

#クラスを定義
class Solution:
    #関数を定義 xは文字列型、返り値はboolean型
    def isPalindrome(self, x: str) -> bool:
        #xを文字列型に変換
        x = str(x)
        #xをリストに変換
        x = list(x)
 　　　　#xを逆順に並べ替えてリストにする
        x_reverse = list(reversed(x))
　　　　 #xとx_reverseが一致している場合Trueを返す
        if x == x_reverse:
            return True
　　　　 #xとx_reverseが一致していない場合Falseを返す
        else:
            return False        
      
"""
解法2
    def isPalindrome(self, x: str) -> bool:
        #xを文字列に変換して"[::-1]"で逆順に並べ替え、元のx(文字列)と一致していればTrueを返す
        return str(x) == str(x)[::-1]
"""

""" 
解法3
    def isPalindrome(self, x: str) -> bool:
        #xを文字列に変換して"[::-1]"で逆順に並べ替え、元のx(文字列)と一致していればTrueを返す
        if str(x) == str(x)[::-1]: return True else: return False
"""

#クラスを定義

class Solution:

#関数を定義 xは文字列型、返り値はboolean型

def isPalindrome(self, x: str) -> bool:

#xを文字列型に変換

x = str(x)

#xをリストに変換

x = list(x)

　　　　#xを逆順に並べ替えてリストにする

x_reverse = list(reversed(x))

　　　　 #xとx_reverseが一致している場合Trueを返す

if x == x_reverse:

return True

　　　　 #xとx_reverseが一致していない場合Falseを返す

else:

return False

"""

解法2

def isPalindrome(self, x: str) -> bool:

#xを文字列に変換して"[::-1]"で逆順に並べ替え、元のx(文字列)と一致していればTrueを返す

return str(x) == str(x)[::-1]

"""

解法3

def isPalindrome(self, x: str) -> bool:

#xを文字列に変換して"[::-1]"で逆順に並べ替え、元のx(文字列)と一致していればTrueを返す

if str(x) == str(x)[::-1]: return True else: return False

"""

別解

class Solution:
    def isPalindrome(self, x: int) -> bool:
        #反転後の数字と比較するための変数x_copyを用意
        x_copy = x
        #反転後のxを0で初期化
        x_reversed = 0
        #xが0より大きければ繰り返す
        while x > 0:
            #一時的な変数tmpにxを10で割った余りを代入。この操作で下1桁を取り出せる
            tmp = x % 10
            #x_reversedにx_reversedを10掛算した数字とtmpを加えた数字を代入する。下1桁目から反転していっている。
            x_reversed = x_reversed*10 + tmp
　　　　　　 #xを10で割った数をxに代入する。この操作で下1桁を除いた数を取り出す。
            x = x//10
        #xが回文であればTrue、そうでなければFalseを返す
        if x_copy == x_reversed:
            return True
        else:
            return False

class Solution:

def isPalindrome(self, x: int) -> bool:

#反転後の数字と比較するための変数x_copyを用意

x_copy = x

#反転後のxを0で初期化

x_reversed = 0

#xが0より大きければ繰り返す

while x > 0:

#一時的な変数tmpにxを10で割った余りを代入。この操作で下1桁を取り出せる

tmp = x % 10

#x_reversedにx_reversedを10掛算した数字とtmpを加えた数字を代入する。下1桁目から反転していっている。

x_reversed = x_reversed*10 + tmp

　　　　　　 #xを10で割った数をxに代入する。この操作で下1桁を除いた数を取り出す。

x = x//10

#xが回文であればTrue、そうでなければFalseを返す

if x_copy == x_reversed:

return True

else:

return False

strに変換するのではなく、intのまま回文であるかを判断することで、資源を無駄に使わずに回文であるかを判断できるのだと思います。

負の整数は、最初に「-」がついているので、回文にはなりません。そのため、正の整数のみ考えれば良いということになります。

Whileの中身は12321を例として考えると、このようなイメージだと思います。

①

元の数：12321%10で、1232と1に分ける。元の数は12321÷10で、1232にする

反転した数：0*10+1 = 1

②

元の数：1232%10で、123と2に分ける。元の数は1232÷10で、123にする

反転した数：1*10+2 = 12

③

元の数：123%10で、12と3に分ける。元の数は123÷10で、12にする

反転した数：12*10+3 = 123

④

元の数：12%10で、1と2に分ける。元の数は12÷10で、1にする

反転した数：123*10+2 = 1232

⑤

元の数：1%10で、1となる。元の数は1÷10で、0にする(今更ながら小数点以下は切り捨て)

反転した数：1232*10+1 = 12321

⑥

元の数：0のためWhileループから抜け出す。

ここまでがWhileループの中身であり、この後にif文で元の数と一致しているかを判定するという流れになります。正直理解できていませんが、実行時間はstrに変換した場合と比べて半分近くまで削減することができました。しかし、この方法では数字をそのまま反転させているだけなのでオーバーフローの可能性があります。解説では元の数の後半部分のみを反転させる考え方でしたが、今回はここまでにします。

コードのみ

class Solution:
    def isPalindrome(self, x: str) -> bool:
        #print(type(x)) 出力はint型
        x = str(x)
        x = list(x)
        x_reverse = list(reversed(x))
        if x == x_reverse:
            return True
        else:
            return False        
"""
解法3
        if str(x) == str(x)[::-1]:
            return True
        else:
            return False        
"""            
"""
解法2
        return str(x) == str(x)[::-1]
"""

class Solution:

def isPalindrome(self, x: str) -> bool:

#print(type(x)) 出力はint型

x = str(x)

x = list(x)

x_reverse = list(reversed(x))

if x == x_reverse:

return True

else:

return False

"""

解法3

if str(x) == str(x)[::-1]:

return True

else:

return False

"""

解法2

return str(x) == str(x)[::-1]

"""

補足・参考・感想

Atcoderでは入力値をinput()を使って入力値を受け取る必要がありますが、LeetCodeは不要、というよりも使ってはならないのでしょうか？inputを使わなくとも初めからxにテストケースの値が入っていました。LeetCodeの仕組みに慣れるまで続けていきたいと思います。

逆順に並べ替える方法はいくつかあるようだったので、いろいろな書き方を勉強し、状況に応じて使えるようになりたいです。

ここまで書いてから解説を見たところ、どうやら文字列型に変換するのは想定解ではないようです。理由はintからstrに変換すると余分に非定常領域(？)(メモリ？)を使用するからとのことでした。intのまま回文であるかを確かめる必要があります。

ただし、単に数字を反転させた場合、反転後の数字が大きくなりすぎてオーバーフローとなるエッジケースが存在します。そこで、数字の後半部分を反転させることで確認する考え方が記載されていました。

難易度はeasyですが、単に実現できれば良いだけでなく、処理の速さや資源の節約をするために色々と調べたり勉強することが大切だと思いました。大変な分野に足を踏み入れてしまったような気がしますが、折れるまで頑張りたいと思います。

次の記事：13. Roman to Integer

記事一覧：LeetCode記事一覧