Valid Palindrome【Java LeetCode#125】

JavaでPalindrome判定を改善してみた

文字列を回文かどうか判定する問題を解くとき、最初に書いたコードにはいくつか問題点がありました。
今回はそれを改善した方法を紹介します。

問題の定義

文字列 s が回文かどうかを判定します。

• 大文字・小文字は区別しない
• アルファベット以外の文字は無視する

例えば：

Input: "A man, a plan, a canal: Panama"
Output: true

Input: "race a car"
Output: false

初版コードの問題点

class Solution {
    int n1 = 48, n2 = 57, n3 = 97, n4 = 122;

    public boolean isPalindrome(String s) {
        String s1  = "";
        s = s.toLowerCase();
        for (char c : s.toCharArray()) {
            if((c >= n1 && c <= n2) || (c >= n3 && c <= n4)){
                s1 += c + "";
            }  
        }

        String s2 = s1;
        int index  = 0;

        for (int i = s2.length()-1; i >= 0; i--) {
            if(s2.charAt(i) != s1.charAt(index)){
                return false;
            }
            index++;
        }

        return true;
    }
}

問題点

String連結が高コスト
s1 += c は毎回新しい String を作るので、長い文字列だと O(n²) になります。

文字列を2つ作って比較している
メモリ効率が悪く、逆順文字列を作る必要があります。

英字の範囲指定が小文字のみ
a-z しか見ていないので、toLowerCase() を忘れるとバグになります。

改善ポイント

StringBuilderを使う → 文字列連結コストを削減

左右ポインタ（two-pointer）で比較 → 逆順コピー不要で O(1) メモリ

Character.isLetterOrDigit() → 英数字判定を安全に行う

改善後のコード

class Solution {
    public boolean isPalindrome(String s) {
        StringBuilder sb = new StringBuilder();
       
        for (char c : s.toCharArray()) {
            if (Character.isLetterOrDigit(c)) {
                sb.append(Character.toLowerCase(c));
            }
        }
    
        int left = 0, right = sb.length() - 1;
        while (left < right) {
            if (sb.charAt(left) != sb.charAt(right)) {
                return false;
            }
            left++;
            right--;
        }

        return true;
    }
}

計算量

時間計算量: O(n)

文字列の長さ n に対して一度ずつ処理するため

空間計算量: O(n)

StringBuilder を使用しているため

まとめ

StringBuilder と two-pointer を使うことで効率的に回文判定が可能

Character.isLetterOrDigit() を使うことで安全に英数字のみを判定

計算量も O(n) で十分高速

執筆者

Javaエンジニア。Hyrox挑戦中。
→ Qiita: @Katsu8998
https://hyrox-dashboard-kahbkakpyuagzybbm6buiz.streamlit.app/
https://leetcode.com/problems/valid-palindrome/solutions/7298370/my-solution-java