前から読んでも後ろから読んでも同じか｜コーディング面接問題

問題

文字列 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 つも無いときは？」と、端の場合を聞かれることもあります

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

まず考える手順

段 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;
}

英字と数字が 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 と組み合わせます

面接での話し方の例

書き始める前に、方針を短く口に出します。

「英数字だけを小文字で取り出して逆と比べれば解けますが、写しのために記憶を O(n) 使います。両端に指を置いて、英数字でない文字はその指だけ進め、英数字どうしなら小文字にして比べながら寄せていけば、記憶は O(1) で済みます。時間はどちらも O(n) です。」

書き終えたら、例を 1 つ手でたどって見せます。

「例 2 の "1-a-2" でたどります。左の指は 1、右の指は 2 を指していて、どちらも英数字です。小文字にしても 1 と 2 で違うので、そこで false を返します。」

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