Is Subsequence
2つの文字列 s と t が与えられます。t の文字をいくつか（0個でも可）削除し、残った文字の順序を保ったまま s にできる場合は true を、そうでない場合は false を返してください。たとえば、ace は abcde の部分列ですが、aec はそうではありません。
関数
- sstring
- 検索する文字列
- tstring
- 文字を削除する対象の文字列
- 戻り値boolean
- 間に抜けがあっても、s を t の中から順番どおりに読み取れる場合は true
制約
1 ≤ s.length ≤ 3 × 1041 ≤ t.length ≤ 5 × 104sとtには小文字の英字のみが含まれています。
例
- 入力
- s = "ace"t = "abcde"
- 出力
- true
- 説明
abcdeからbとdを削除すると、aceが同じ順序で残ります。
- 入力
- s = "aec"t = "abcde"
- 出力
- false
- 説明
tには3つの文字がすべて含まれていますが、唯一のcは唯一のeより前にあります。インデックス4のeを使うと、その右側にはcが残っていません。
- 入力
- s = "moon"t = "monsoon"
- 出力
- true
- 説明
monsoonのインデックス0にあるm、インデックス1と4にあるo、インデックス6にあるnを使います。間の文字は削除されます。
提出時に隠しテスト+20件
発展問題
t が変わらないままで、100万個の異なる文字列 s をそれと照合する必要があるとします。毎回 t 全体を読み直すよりも速く照合できるように、t をどのように準備しますか？
ヒント
1つずつ開いてください。開くたびに少しずつ答えに近づきます。
sの最初の文字を見てください。tにあるその文字のどのコピーを使うべきでしょうか？最も早いコピーを使います。後のコピーを選ぶと、
sの残りの部分に使えるtが少なくなるだけなので、最も早い選択が不利になることはありません。sを指すインデックスと、tを指すインデックスを1つずつ保持します。tを1文字ずつ進み、一致するたびにsのインデックスを進め、最後にsの末尾に到達したかどうかを確認します。
解説
部分列では t の文字をどこでも飛ばせるため、s を t の中に配置する多くの方法を試さなければならないように思えるかもしれません。しかし、その必要はありません。s の各文字を置ける最も早い位置で一致させる方法は、ほかのどの選択よりも悪くなることはありません。そのため、探索は2つのポインターを使った左から右への1回の走査で済みます。
接頭辞に対する動的計画法
正しいが、最大のテストでは終わらない
考え方
より小さな問いを考えます。s の最初の i 文字は、t の最初の j 文字に含められるでしょうか？その答えを dp[i][j] とします。t[:j-1] に含められるなら、t[j-1] を削除できるため、t[:j] にも含められます。s[i-1] が t[j-1] と等しければ、その文字を使うこともできます。その場合、s の最初の i-1 文字は t[:j-1] に含められなければなりません。したがって、dp[i][j] = dp[i][j-1] or (s[i-1] == t[j-1] and dp[i-1][j-1]) となり、s の空の接頭辞はどこにでも含められます。
行 i が参照するのは行 i-1 だけなので、長さ m+1 の行が2つあれば十分です。答えは最後の行の最後のセルです。
これは最長共通部分列を求めるときに作るものと同じ表で、正しい方法ですが、すべてのセルを埋めます。s が25,000文字、t が50,000文字の場合、セル数は1.25 × 10^9となり、2つの文字列を1回ずつ走査するのに必要な量をはるかに上回ります。
アルゴリズム
prevというm+1個の値を持つ行を作成し、すべてをtrueにします。空のsはtのすべての接頭辞に適合します。- 1 から
nまでの各iについて、cur[0] = falseを持つ行curを作成します。 - 1 から
mまでの各jについて、cur[j]をcur[j-1]に設定するか、s[i-1]とt[j-1]が等しい場合はprev[j-1]に設定します。 prevをcurに置き換えます。prev[m]を返します。
def isSubsequence(s, t):
n, m = len(s), len(t)
# prev[j]: the first i-1 letters of s fit inside t[:j]. An empty s fits anywhere.
prev = [True] * (m + 1)
for i in range(1, n + 1):
cur = [False] * (m + 1)
for j in range(1, m + 1):
cur[j] = cur[j - 1] or (s[i - 1] == t[j - 1] and prev[j - 1])
prev = cur
return prev[m]貪欲マッチングを使った2つのポインター
考え方
tを左から右へ読み、まだ必要なsの次の文字を指すポインターiを保持します。t[j]がs[i]と等しい場合はそれを使い、iを進めます。どちらの場合も、jを進めます。iがsの末尾に達したら、すべての文字が順番どおりに見つかったことになります。
最初に一致した文字を選んでも安全なのはなぜでしょうか。ある有効な配置でs[i]の後ろの方にある文字を使っているとします。それを最も早い位置にある文字と入れ替えても順序は保たれ、残りのsのためにtの右側により多くの部分を残せるため、貪欲な選択によって、存在する配置を失うことはありません。monsoonに含まれるmoonでは、ポインターはインデックス1のoを取り、nとsを飛ばし、インデックス4のoを取り、インデックス6のnで終了します。
jはtの各文字を一度ずつ確認し、iは前に進むだけなので、ループの実行回数は最大でもm回です。必要なメモリーは2つのインデックスだけです。
アルゴリズム
sに対してi = 0、tに対してj = 0を設定します。- 両方のインデックスがそれぞれの文字列の範囲内にある間、
s[i]とt[j]を比較します。 - 等しい場合は、
iを増やします。 - いずれの場合も
jを増やします。 iがsの長さと等しいかどうかを返します。
def isSubsequence(s, t):
i = j = 0
while i < len(s) and j < len(t):
if s[i] == t[j]:
i += 1
j += 1
return i == len(s)
落とし穴と境界ケース
2ポインターのループは短く、バグは端の処理に潜んでいます。
sの各文字を、前回一致した位置より後ろではなく、tのどこにでもあるか検索してしまうこと。これでは、順序が崩れているabcde内のaecも受け入れてしまいます。- 同じ文字を2回使ってしまうこと。
noonはmoonの部分列ではありません。moonにはnが1つしかなく、インデックス3にあるため、noonの最初と最後の文字の両方には使えません。 jがtの末尾に達したかどうかを返してしまうこと。sが見つかったかどうかにかかわらず、ループはそこで終わることがよくあります。判断に使えるのはiだけです。sがtより長い場合があることを忘れること。abに対するabcはfalseを返す必要があります。tの要素がなくなった時点でループが停止すれば、そうなります。iがsの末尾に達した後でs[i]を読み取ってしまうこと。PythonやJavaではその読み取りで例外が発生するため、比較する前にiを確認してください。
よくある質問4
Is Subsequence の時間計算量は何ですか？
2ポインター解法の実行時間はO(n + m)で、nとmはそれぞれsとtの長さです。また、追加メモリはO(1)使用します。実際には、ループは最大でもmステップで終了します。接頭辞テーブルの計算にはO(n × m)の時間がかかります。
部分列の判定で貪欲な2ポインター手法が機能するのはなぜですか？
sの文字をtの中で可能な限り早い位置に対応させると、残りの文字に使えるtの部分が最も長く残ります。後の出現箇所を使う対応は、順序を崩さずにより早い箇所を使う形に変更できるため、対応が存在するなら、貪欲法でそれを見つけられます。
同じ t に対して複数の文字列をすばやく確認するにはどうすればよいですか？
tを一度だけ前処理します。各文字について、その文字が現れるインデックスをソートしたリストに保存します。s[i]を配置するには、前回一致したインデックスより後にある最初のインデックスを、その文字のリストから二分探索します。これにより、各チェックの計算量はO(m)ではなくO(n log m)になります。
部分列と部分文字列の違いは何ですか？
部分文字列は連続した文字のまとまりですが、部分列は順序を保つ限り文字を飛ばすことができます。ace は abcde の部分列ですが、部分文字列ではありません。すべての部分文字列は部分列ですが、その逆は成り立ちません。
似た問題
同じ考え方を使う問題です。2〜3問解くとパターンが身につきます。
Python
def isSubsequence(s, t):
# ここにコードを書いてくださいケース1
ケース2
ケース3
入力
s = "ace" t = "abcde"
期待値
true