LeetCode / Palindrome Number

https://leetcode.com/problems/palindrome-number/

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

Example 1:

Input: 121
Output: true
Example 2:

Input: -121
Output: false
Explanation: From left to right, it reads -121. From right to left, it becomes 121-. Therefore it is not a palindrome.
Example 3:

Input: 10
Output: false
Explanation: Reads 01 from right to left. Therefore it is not a palindrome.

Follow up:

Coud you solve it without converting the integer to a string?

数値が回文になっているか判定する問題です。
Follow upにあるように、integerをstring型にして回文か判定する手法"以外"を探せ、と言われています。

回答・解説

解法1

とはいえまずは、integerをstringに変換し回文かどうか判定するコードを示しておきます。

class Solution:
    def isPalindrome(self, x: int) -> bool:
        return str(x) == str(x)[::-1]

これは簡単なので、どれだけ短く書けるかが勝負ですね。問題はstringを使わない方法です。

解法2

stringを使わずintegerのまま判定する際、全桁を比較してしまうとオーバーフローが起こり得ます。
そこで、上X桁と下X桁だけを比較して判定しよう、というのが2つ目のアイデアです。
つまり、"1221"であれば上2桁の"12"と"21"だけを取り出して判定し、
"121"などと桁数が奇数であれば、真ん中の桁は除いて判定します。

class Solution:
    def isPalindrome(self, x: int) -> bool:
        if x < 0 or (x % 10 == 0 and x != 0):
            return False
        revN = 0
        while x > revN:
            revN = revN * 10 + x % 10
            x //= 10
            print(x, revN)
        return x == revN or x == revN//10

上記では、負の値や下1桁が0の正の値といった回文にならないものは先にfalseと判定した上で、
xで上X桁を、revNで下X桁（をひっくり返した値）を計算します。
while loopをxの桁数がrevNの桁数を上回る間だけ回します。
上X桁は、x //= 10 と元の値を10で割った商を求めることで計算できます。
下X桁をひっくり返した値は、revN = revN * 10 + x % 10 と元の値を10で割った余りを出しながら、loopで10を掛けることで計算できます。
最後に、元の値の桁数が偶数の場合はx == revNで判定し、奇数の場合はx == revN//10で真ん中の桁は除いて判定します。

正直解法1の方が処理時間も明らかに短いし、stringを使わない動機は？なんですが、オーバーフローを避けるため桁を分けて判定するアイデアはいつか役に立つかも？しれません。