Valid Palindrome
文字列 s が与えられます。英字と数字だけを残し、大文字と小文字を同じ文字として扱って、残った文字列が左から読んでも右から読んでも同じかどうかを判定してください。同じなら true、そうでなければ false を返します。
.、!、?、:、;、-、_ など、それ以外の文字はすべて無視します。s に英字も数字も含まれていない場合、何も残らず、空文字列は回文とみなされます。
関数
- sstring
- 確認するテキスト（句読点を含む）
- 戻り値boolean
- 大文字と小文字を区別せずに、s の文字と数字を両方向から読んで同じ場合は true
制約
1 ≤ s.length ≤ 5 × 104sには英字、数字、句読点. ! ? : ; - _が含まれ、空白はありません。
例
- 入力
- s = "Was_it_a_car_or_a_cat_I_saw?"
- 出力
- true
- 説明
- アンダースコアと疑問符を取り除き、大文字を小文字にすると、
wasitacaroracatisawになります。これは逆から読んでも同じです。
- 入力
- s = "race-a-car"
- 出力
- false
- 説明
- ハイフンを除くと、テキストは
raceacarです。右から読むとraceではなくracaで始まります。中央のeの鏡像となる文字はaなので、答えはfalseです。
- 入力
- s = "Step-on-no-pets!"
- 出力
- true
- 説明
- 保持されるテキストは
steponnopetsです。大文字のSは大文字と小文字が区別されないため最後のsと一致し、ハイフンと!は関係ありません。
提出時に隠しテスト+25件
発展問題
クリーニングした s のコピーを作らずに、追加メモリ O(1) で判定できますか？
ヒント
1つずつ開いてください。開くたびに少しずつ答えに近づきます。
ひとまず句読点のことは忘れてください。回文チェックでは、実際に
sのどの文字を比較し、どのような組み合わせで比較しますか？最初の文字または数字は最後の文字または数字と比較され、2番目の文字または数字は後ろから2番目の文字または数字と比較される、といった具合に、小文字で比較されます。句読点は比較に含まれないため、次のペアを見つける邪魔になるだけです。
先頭からインデックスを1つ進め、末尾から1つ戻します。文字でも数字でもない文字をインデックスが通り過ぎるように進め、両方の文字が残っている場合はその2文字を比較し、インデックスが一致したら停止します。
解説
回文チェック自体はおなじみのものです。残す最初の文字は最後の文字と一致し、2番目の文字は後ろから2番目の文字と一致し、以下同様です。この方法が少し厄介なのは、比較する文字がsの左右対称のインデックスにあるとは限らない点です。句読点が両側に不均等に散らばっているためです。先に句読点を取り除くか、2つのポインターを互いに向かって進めながら句読点を飛ばすことができます。
文字列をクリーンアップしてから、逆順にした文字列と比較します
考え方
問題が実際に尋ねている対象のテキストを作ります。sを順に調べ、各文字または数字を小文字のまま残し、それ以外はすべて飛ばします。Step-on-no-pets!の場合はsteponnopetsになります。ここでの問いは、単純な回文の問題です。このテキストは逆順にしたものと等しいでしょうか？
これは、問題が無視するよう指示した文字だけを取り除き、無視するよう指示した大文字・小文字の違いをなくしているため、正しい方法です。sに文字も数字も含まれていない場合、処理後のテキストは空になり、空のテキストは逆順にしても同じなので、特別な場合分けをせずに答えはtrueになります。
各文字は、処理のために一度、比較のためにもう一度読み取られるので、時間計算量はO(n)です。処理後のコピーとその逆順の作成には、追加でO(n)のメモリが必要です。次の方法では、このコストを取り除きます。
アルゴリズム
- 空のテキスト
cleanedを作成します。 sの各文字について、英字または数字であれば、小文字にして追加します。cleanedを反転します。cleanedがその反転したものと等しいかどうかを返します。
def isPalindrome(s):
cleaned = [ch.lower() for ch in s if ch.isalnum()]
return cleaned == cleaned[::-1]句読点をスキップする2つのポインター
考え方
クリーニングしたコピーは、反転した文字を比較できるようにするためだけのものです。sを直接比較しても同じことができます。最初のインデックスにleftを、最後のインデックスにrightを置きます。各ステップで、leftが句読点を指していたら右へ移動し、rightが句読点を指していたら左へ移動します。両方が文字または数字を指したら、小文字にして比較します。一致しなければfalse、一致すれば両方のポインターを内側へ進めます。
なぜこれで同じ判定になるのでしょうか？ポインターは常に、それぞれの端から次に残される文字で止まるため、（最初に残される文字、最後に残される文字）、（2番目に残される文字、最後から2番目に残される文字）というペアを順に調べます。これは、反転して比較する方法で調べるペアとまったく同じです。Abc-dcbXでは最初のペアはAとXで、1回の比較で答えはfalseになります。
各ステップで少なくとも一方のポインターが移動し、両者が出会うと停止するため、ループの実行回数は最大でもn回です。2つのインデックス以外は何も保存しないため、追加メモリはO(1)です。
アルゴリズム
left = 0とright = n-1を設定します。left < rightの間、s[left]が英字または数字でなければ、leftを増やして続行します。- そうでなければ、
s[right]が英字または数字でない場合、rightを減らして続行します。 - そうでなければ、2つの文字を小文字にして比較します。異なれば
falseを返し、一致すれば両方のポインターを内側に移動します。 - ポインターが出会ったら、
trueを返します。
def isPalindrome(s):
left, right = 0, len(s) - 1
while left < right:
if not s[left].isalnum():
left += 1
elif not s[right].isalnum():
right -= 1
elif s[left].lower() != s[right].lower():
return False
else:
left += 1
right -= 1
return True
落とし穴と境界ケース
ほとんどのバグは、スキップする文字と大文字・小文字の扱いが原因です。
- 生の文字列に対して
s[i]とs[n-1-i]を比較すること。ハイフンを取り除けばa-baは回文ですが、インデックス 1 の-に対応する生の文字列の反対側の文字は、インデックス 2 のbです。 - どちらか一方のポインターだけが句読点を指しているときに、両方のポインターを動かすこと。片側ずつスキップしてください。そうしないと、両側の位置がずれてしまいます。
- もう一方のポインターを通り越して実行される内側のループで、句読点をスキップすること。
?!-_の場合、上限のない内側のループは文字列の末尾を越えてしまいます。移動するたびにleft < rightのチェックを行ってください。 - 数字を無視すること。
0Pはfalseです。数字の0は残して比較し、文字のpとは別のものとして扱います。 - 何も残らなかった場合に
falseを返すこと。.のように句読点だけの文字列は、クリーニング後のテキストが空になり、回文とみなされます。 12321のように数字だけで構成された文字列は、PHP と R では数値として扱われることがあります。まず文字列に変換してください。
よくある質問4
Valid Palindrome の時間計算量はどれくらいですか？
どちらの方法も、すべての文字を定数回だけ調べるため、実行時間は O(n) です。先にクリーニングする方法では、コピーを作成するために追加で O(n) のメモリを使用します。2ポインター版では、2つのインデックスだけを保持するため、追加メモリは O(1) です。
英数字以外の文字を無視して、回文かどうかを確認するにはどうすればよいですか？
文字列の両端にそれぞれポインターを置きます。文字または数字ではない文字をポインターが通り過ぎるように動かし、両方のポインターが文字または数字を指したら、小文字にして比較します。ポインターが出会うまで比較したすべてのペアが一致すれば、その文字列は回文です。
空文字列は回文ですか？
はい。空のテキストはどちらの方向から読んでも同じなので、すべての文字が無視される?!-_のような文字列はtrueを返します。どちらの方法でも、追加のコードなしでこの結果が得られます。クリーニング後のテキストはその逆順のテキストと等しく、2つのポインターは異なる文字のペアを見つけません。
文字列を反転する代わりに、なぜ2つのポインターを使うのでしょうか？
反転には、クリーンアップしたコピーと反転したコピーが必要で、追加メモリは O(n) です。2つのポインターで同じ組をその場で比較でき、最初の不一致が見つかった時点で停止できます。多くの場合、数ステップで停止します。面接官は通常、追加の質問としてこの方法を求めます。
似た問題
同じ考え方を使う問題です。2〜3問解くとパターンが身につきます。
Python
def isPalindrome(s):
# ここにコードを書いてくださいケース1
ケース2
ケース3
入力
s = "Was_it_a_car_or_a_cat_I_saw?"
期待値
true