Is Subsequence
2つの文字列 s と t が与えられます。文字の順序を保ったまま t からいくつかの文字を削除（削除しなくてもよい）して 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を使います。その間の文字は削除されます。
発展問題
tを固定したまま、100万個の文字列sを照合する場合、毎回t全体を読むよりも速く判定できるように、tをどのように準備しますか？
ヒント
1つずつ開いてください。開くたびに少しずつ答えに近づきます。
sの最初の文字を見てください。tの中にあるその文字のどのコピーを使うべきでしょうか？最も早いコピーを使います。後のコピーを選ぶと、残りの
sに使えるtが少なくなるだけなので、最も早い選択が不利になることはありません。sのインデックスを1つ、tのインデックスを1つ保持します。tを1文字ずつ進み、一致するたびにsのインデックスを進め、最後にsの末尾に到達したかどうかを確認します。
解説
部分列では、tの文字をどこでも飛ばすことができるため、sをさまざまな位置に置いて試すことが考えられます。その必要はありません。sの各文字を置ける最も早い位置で一致させる方法は、ほかのどの選択よりも不利になることはないので、2つのポインターを使って左から右へ1回走査すれば判定できます。
接頭辞に対する動的計画法
正しいが、最大のテストでは終わらない
考え方
dp[i][j]を、sの最初のi文字がtの最初のj文字に収まるかどうかを表すものとします。t[j-1]を使わなくてもすでに収まる場合、またはs[i-1]がt[j-1]と等しく、最初のi-1文字がt[:j-1]に収まる場合に、収まります。空の接頭辞はどこにでも収まり、行iが参照するのは行i-1だけなので、長さm+1の行が2つあれば十分です。
この表ではすべてのセルを埋めます。sが25,000文字、tが50,000文字の場合、セルの数は1.25 × 10^9です。
アルゴリズム
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つのポインター
考え方
必要な s の次の文字を指すポインター i を保持し、t の中で最初に見つかるその文字を選びます。この選択は安全です。有効な配置で s[i] の後のほうの出現箇所を使う場合でも、最も早い出現箇所に置き換えれば順序が保たれ、残りの s のために t のより多くの部分を残せます。したがって、配置が存在するなら、貪欲法で見つけられます。
ループでは t の各文字を最大 1 回読み取り、2 つのインデックスを保持します。時間計算量は O(n + m)、メモリ計算量は O(1) です。
アルゴリズム
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)
落とし穴と境界ケース
t内の前の一致位置より後ではなく、t内のどこにあるかを調べながら、sの各文字を探すこと。これでは、abcdeの部分列としてaecを受け入れてしまいます。- 同じ文字を2回使うこと。
noonはmoonの部分列ではありません。インデックス3にある唯一のnを、最初と最後の文字の両方に使うことはできません。 jがtの末尾に達したかどうかを返すこと。sが見つかったかどうかにかかわらず、ループはそこで終わることがよくあります。判断できるのはiだけです。tの文字が尽きても処理を止めないこと。abに対するabcはfalseを返す必要があります。iがsの末尾に達した後でs[i]を読み取ること。PythonやJavaでは、その読み取りで例外が発生するため、比較する前にiを確認してください。
よくある質問3
Is Subsequence の時間計算量は何ですか？
2 ポインター解法は、n と m がそれぞれ s と t の長さであるとき、O(n + m) 時間で実行され、追加メモリは O(1) です。ループは最大でも m ステップ後に停止します。接頭辞テーブルは O(n × m) 時間がかかります。
Is Subsequence は最長共通部分列とどのように関係していますか？
s が t の部分列であるのは、最長共通部分列の長さが n、つまり s のすべての文字を含む場合に限ります。最初の方法で使う接頭辞テーブルは、その問題のために作成するものです。ここでは s のすべての文字が含まれるかどうかだけを知ればよいので、貪欲な走査で十分です。
部分列と部分文字列の違いは何ですか？
部分文字列は連続する文字のまとまりですが、部分列は順序を保てば文字を飛ばすことができます。aceはabcdeの部分列ですが、部分文字列ではありません。すべての部分文字列は部分列ですが、その逆は成り立ちません。
似た問題
同じ考え方を使う問題です。2〜3問解くとパターンが身につきます。
def isSubsequence(s, t):
# ここにコードを書いてくださいテスト #1
テスト #2
テスト #3
引数
s = "ace" t = "abcde"
期待される出力
true