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です。
発展問題
空白と句読点を読み飛ばし、大文字と小文字を区別しないように2つのポインターをどう変更すれば、Was it a car or a cat I sawが回文として判定されるでしょうか？
ヒント
1つずつ開いてください。開くたびに少しずつ答えに近づきます。
sが回文である場合、最初の文字はどの文字と等しくなければなりませんか？インデックス
iの文字は、インデックスn-1-iの文字と等しくなければなりません。このような各ペアは一度だけ確認すればよいため、インデックスの半分だけで十分です。先頭に1つ、末尾に1つインデックスを置きます。2つの文字を比較し、一致しなければ
falseを返し、両方のインデックスが出会うまで内側へ1つずつ移動させます。
解説
回文は逆順にしても元の文字列と同じなので、逆順の文字列を作って比較できます。コピーを作る必要はありません。最初の文字は最後の文字と、2番目の文字は最後から2番目の文字と一致する必要があり、以降も同様です。2つのインデックスを内側に向かって進めれば、その場でこれらの文字の組を調べ、最初に不一致が見つかった時点で停止できます。
文字列をその逆順の文字列と比較する
考え方
sを逆順にして比較します。racecarを逆順にしてもracecar、coddyを逆順にするとyddocです。文字列が逆順にしたものと等しいとき、かつそのときに限り、どちら向きに読んでも同じになります。
実行時間はO(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回現れるため、左半分を調べれば十分です。racecar では、ペアは (0, 6)、(1, 5)、(2, 4) です。インデックス3の中央の e には、対応する文字は必要ありません。
最初に異なるペアが見つかった時点で答えが 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つのインデックスを保持するため、追加の領域は O(1) です。s とその逆順の文字列を比較する方法は、コードは短く書けますが、n 文字の2つ目の文字列を作成します。
回文文字列を判定する時間計算量はどれくらいですか？
長さが n の文字列の場合、O(n) です。2つのポインターによるチェックでは比較は最大でも n / 2 回で、最初の不一致で停止するため、coddy の場合は比較が1回です。
1文字は回文ですか？
はい、どちらの方向から読んでも同じです。2つのポインターを使うループでは、left と right はどちらもインデックス0から始まり、ループは一度も実行されず、関数は true を返します。
似た問題
同じ考え方を使う問題です。2〜3問解くとパターンが身につきます。
def isPalindrome(s):
# ここにコードを書いてくださいテスト #1
テスト #2
テスト #3
引数
s = "racecar"
期待される出力
true