ツーポインタで回文を判定する

ツーポインタ問題 10

英字と数字だけを見て、大文字と小文字を区別せずに回文かどうかを調べる。両端に置いた 2 つの指を、まん中へ寄せていく考え方 (ツーポインタ) の練習です。

海外で定番の問題リスト 4 本のうち 4 本に入っています (Blind 75、NeetCode 150、Grind 75、LeetCode Top Interview 150)

問題

文字列 s を受け取ります。s の中の英字と数字だけを見て、前から読んでも後ろから読んでも同じ並び (回文) なら true、そうでなければ false を返す関数を書いてください。

英字の大文字と小文字は区別しません。A と a は同じ文字と見なします
空白や記号など、英字と数字のほかの文字は読み飛ばします
英字と数字が 1 つも無いときは true を返します
s の長さは 0 以上 10000 以下で、ASCII の文字 (半角の英字、数字、空白、記号) だけでできています

入力と出力の例

例 1

英字だけを小文字で読むと topspot になり、逆から読んでも同じです。

s = "Top spot!"

true

例 2

1a2 を逆から読むと 2a1 なので、回文ではありません。

s = "1-a-2"

false

例 3

英字も数字も無いので、回文と見なします。

s = "?! .,"

true

面接での聞かれ方

面接では、短い一言で渡されることが多いです。

「文字列が回文かどうかを判定してください。記号は無視して、大文字小文字も区別しません」
書き終えたあとに「余分な記憶を使わずに書けますか？」と続けて聞かれます
「英数字が 1 つも無いときは？」と、端の場合を聞かれることもあります

どの文字を読み飛ばすのか、大文字と小文字を同じに見るのかを、最初に確かめておきます。ここは問題ごとに決まりが違うので、思い込みで書き始めないようにします。

ヒント

まだ開いていません

付箋は 3 枚。下の段ほど答えに近づきます

ヒント 2
ヒント 3答えに近い

アルゴリズムのチートシートの「配列と文字列」に、この型の要点を表とコードでまとめています。

配列と文字列の問題は、全部の組を調べると手間が大きくなる所を、窓や左右の添字で減らす形が多いです。

まず考える手順

段 1

まずは素直に、英字と数字だけを取り出して小文字にした、新しい文字列を作ります。それを逆にした物と比べ、同じなら回文です。これでも正しく動きますが、写しの文字列を 2 つ作るので、記憶を O(n) 使います。

段 2

写しを作らずに比べるには、左の端と右の端に 1 つずつ指を置きます。左の指の文字と右の指の文字が同じなら、左は 1 つ右へ、右は 1 つ左へ寄せます。違えば、その時点で回文ではありません。

段 3

指が英字と数字のほかの文字を指していたら、その指だけを 1 つ進めて、比べるのは後に回します。比べるときは、どちらも小文字にしてから比べます。2 つの指が出会うか追い越したら、全部を比べ終えたので true を返します。

解答

Python

def is_palindrome(s):
    def ok(ch):
        if not ch.isascii():
            return False
        return ch.isalnum()

    def low(k):
        return s[k].lower()
    i = 0
    j = len(s) - 1
    while i < j:
        if not ok(s[i]):
            i += 1
        elif not ok(s[j]):
            j -= 1
        elif low(i) != low(j):
            return False
        else:
            i += 1
            j -= 1
    return True

JavaScript

function isPalindrome(s) {
  const re = /[A-Za-z0-9]/;
  const ok = (c) => re.test(c);
  const low = (k) => {
    return s[k].toLowerCase();
  };
  let i = 0;
  let j = s.length - 1;
  while (i < j) {
    if (!ok(s[i])) {
      i++;
      continue;
    }
    if (!ok(s[j])) {
      j--;
      continue;
    }
    if (low(i) !== low(j)) {
      return false;
    }
    i++;
    j--;
  }
  return true;
}

Go

func isPalindrome(
	s string,
) bool {
	ok := func(c byte) bool {
		switch {
		case 'a' <= c && c <= 'z':
		case 'A' <= c && c <= 'Z':
		case '0' <= c && c <= '9':
		default:
			return false
		}
		return true
	}
	low := func(k int) byte {
		c := s[k]
		if 'A' <= c && c <= 'Z' {
			c += 'a' - 'A'
		}
		return c
	}
	i, j := 0, len(s)-1
	for i < j {
		if !ok(s[i]) {
			i++
			continue
		}
		if !ok(s[j]) {
			j--
			continue
		}
		if low(i) != low(j) {
			return false
		}
		i++
		j--
	}
	return true
}

英字と数字が 1 つも無いときは、指が寄るあいだに 1 回も比べないまま出会うので、そのまま true になります。空の文字列なら、最初から i < j が成り立たず、すぐに true を返します。

計算量

時間は O(n) です。どの繰り返しでも、2 つの指のどちらかが必ず 1 つ以上寄るので、合わせて n 回ほどで終わります
使う記憶は O(1) です。持つのは 2 つの位置だけで、写しの文字列を作りません
段 1 の、写しを作って逆と比べる書き方は、時間は O(n) で同じですが、記憶を O(n) 使います

よくある間違い

大文字と小文字をそろえずに比べる。例 1 の T と t を別の文字と見て、false を返してしまいます。比べる直前に両方を小文字にします
読み飛ばすときに両方の指を進める。片方だけが記号を指しているのに両方を進めると、比べるはずの文字を飛ばしてしまいます。進めるのは記号を指している指だけです
Python の isalnum だけで英数字を判定する。 isalnum は ASCII のほかの文字、たとえば全角の数字にも True を返します。この問題は ASCII の範囲だけを見るので、isascii と組み合わせます

解答を動かした版 Python 3.12.14Node.js 22.23.4Go 1.24.2確認日 2026年10月24日

def is_palindrome(s: str) -> bool: """ Goal: 何を返すか idea1: まず思いつく案 -> runtime: O(?) space: O(?) idea2: もっと速い案 -> runtime: O(?) space: O(?) edge case: 空、1 つだけ、など """ # ここに書きます pass # 「実行」を押すと、この行の結果が出ます print(is_palindrome("Top spot!"))