Palindrome String
文字列は、levelのように、左から右に読んでも右から左に読んでも同じになるとき、回文です。小文字の英字からなる文字列sを受け取り、sが回文ならtrueを、そうでなければfalseを返す関数を書いてください。
関数
- sstring
- 確認する小文字の文字列
- 戻り値boolean
- 文字列 s が両方向から読んでも同じ場合は true
制約
1 ≤ s.length ≤ 5 × 104sには小文字の英字のみ（aからz）が含まれます。
例
- 入力
- s = "racecar"
- 出力
- true
- 説明
- 外側から内側へ比較します。
rとr、aとa、cとc。中央のeには対応する文字がなく、必要もないので、答えはtrueです。
- 入力
- s = "abba"
- 出力
- true
- 説明
- 長さが偶数の場合、すべての文字にペアがあります。2つの
aは一致し、2つのbも一致するため、答えはtrueです。
- 入力
- s = "coddy"
- 出力
- false
- 説明
- 最初の文字
cと最後の文字yはすでに異なるため、coddyは回文ではなく、答えはfalseです。
提出時に隠しテスト+16件
発展問題
たとえば Was it a car or a cat I saw のような文は、大文字と小文字、空白、句読点を無視すると回文になります。それらの文字を飛ばすには、2つのポインターをどのように変更すればよいでしょうか？
ヒント
1つずつ開いてください。開くたびに少しずつ答えに近づきます。
sが回文である場合、その最初の文字はどの文字と等しくなければなりませんか？インデックス
iの文字は、インデックスn-1-iの文字と等しくなければなりません。このような各ペアは一度だけ確認すればよいため、インデックスの半分を調べれば十分です。先頭に1つ、末尾に1つインデックスを置きます。2つの文字を比較し、一致しなければ
falseを返し、両方のインデックスが出会うまで内側へ1歩ずつ移動させます。
解説
回文は逆順にしても元の文字列と等しいため、直接確認するには逆順の文字列を作って比較します。よりよい確認方法では、何も作りません。最初の文字は最後の文字と、2番目の文字は最後から2番目の文字と一致する必要があり、同様に中央に向かって確認します。2つのインデックスを内側に向かって進め、その場で各ペアを調べ、最初に不一致が見つかった時点で停止します。
文字列をその逆順の文字列と比較する
考え方
sを両方向から同じように読むということは、sが逆順にしたものと等しいということです。そこで逆順にして比較します。racecarを逆順にしてもracecarのままで、coddyを逆順にするとyddocになり、異なります。
逆順の文字列を作って比較すると、どちらも各文字に一度ずつアクセスするため、時間計算量はO(n)です。逆順のコピーにはさらにn文字分が必要なので、追加の空間計算量もO(n)です。n = 5 × 10^4の場合、比較するためだけに50,000文字を作り、その後破棄することになります。
また、毎回すべての処理を行います。coddyは先頭と末尾の文字だけで判定できますが、この方法では確認する前に5文字すべてを逆順にします。
アルゴリズム
- 言語の逆順関数を使うか、最後の文字から最初の文字までループして、
sを逆順にします。 - 逆順にしたものを
sと比較します。 - それらが等しければ
trueを、そうでなければfalseを返します。
def isPalindrome(s):
return s == s[::-1]両端からの2つのポインター
考え方
反転すると、インデックス i の文字はインデックス n-1-i に移動するため、すべての i について s[i] が s[n-1-i] と等しい場合に限り、s は逆順にしたものと完全に一致します。このリストでは各ペアが2回現れるので、左半分だけを確認すれば十分です。left をインデックス0に、right をインデックス n-1 に置き、2つの文字を比較して、両方のポインターを内側へ1つ進めます。
ポインターが出会うか、すれ違ったら停止します。racecar ではインデックスのペア (0, 6)、(1, 5)、(2, 4) を確認し、その後、ペアを必要としない中央の e があるインデックス3で出会います。abba では (0, 3) と (1, 2) を確認した後、すれ違います。最初に異なるペアが見つかれば、答えは false だと証明できるため、その場で返します。coddy は1回の比較で判定できます。
比較回数は最大でも n / 2 回なので、時間計算量は O(n) です。使用するメモリは2つのインデックスだけなので、空間計算量は O(1) です。例外はRです。まず文字列を文字コードのベクトルとして読み込むため、O(n) のコストがかかります。
アルゴリズム
left = 0、right = n-1を設定します。left < rightである間、s[left]とs[right]を比較します。- 異なる場合は、
falseを返します。 - そうでなければ、
leftに1を加え、rightから1を引いて、繰り返します。 - ポインターが一致するか交差したら、すべてのペアが一致しています。
trueを返します。
def isPalindrome(s):
left, right = 0, len(s) - 1
while left < right:
if s[left] != s[right]:
return False
left += 1
right -= 1
return True
落とし穴と境界ケース
ループは短いため、誤りは境界条件と戻り値の文にあります。
- 1組でも一致した時点で
trueを返すこと。abcaは外側の組を通過しますが、内側の組で失敗するため、trueを返すのはループ終了後に限られます。 rightをn-1ではなくnから始めること。これでは末尾を越えて読み取ってしまいます（Cでは終端の'\0'まで読み取ります）。LuaとRではインデックスが1からnまでなので、そちらではrightをnから始めます。- 文字列をアドレスで比較すること。Cでは
reversed == sは2つのポインターを比較するため、新しく作成したコピーに対しては常にfalseになります。strcmpを使いましょう。 - ループ内で
result = result + chを使って逆順の文字列を組み立てること。各ステップでそれまでの文字列全体をコピーするため、50,000文字では約1.25 × 10^9回の文字コピーが発生します。 - 整数でSwiftの文字列をインデックス指定すること。これはコンパイルできません。独自のインデックスを使って
s.utf8を走査するか、文字を配列にコピーしてください。
よくある質問4
文字列が回文かどうかを確認するにはどうすればよいですか？
最初の文字と最後の文字、2番目の文字と後ろから2番目の文字というように、中央に向かって比較します。いずれかのペアが異なれば、その文字列は回文ではありません。すべてのペアが一致すれば、回文です。両端から始めて内側に進む2つのインデックスを使えば、これを1回の走査で行えます。
追加のメモリを使わずに回文かどうかを確認できますか？
はい。2ポインターによるチェックでは、文字をその場で読み取り、2つのインデックスだけを保存するため、追加の領域は O(1) です。s とその逆順の文字列を比較する方法は、より短く書けますが、n 文字の2つ目の文字列を作成します。
回文文字列を確認する時間計算量はどれくらいですか？
長さが n の文字列の場合、計算量は O(n) です。2つのポインターによるチェックでは比較回数は最大でも n / 2 回で、最初に不一致が見つかるとそこで停止するため、最初と最後の文字が異なる文字列は1回の比較で判定されます。
1文字は回文ですか？
はい。1文字はどちらの方向から読んでも同じなので、答えは true です。2つのポインターを使うループでは、left と right はどちらもインデックス0から始まり、ループは一度も実行されず、関数は true を返します。
似た問題
同じ考え方を使う問題です。2〜3問解くとパターンが身につきます。
Python
def isPalindrome(s):
# ここにコードを書いてくださいケース1
ケース2
ケース3
入力
s = "racecar"
期待値
true