Subsequenceという問題を解きます。(subsequene)かどうかを判定せよ。sとtは英語の小文字のみを含む文字列で、tは長い(50万文字)こともあるが、sは短い文字列(100文字以下)であると仮定してよい。今日も窓辺でプログラム部分列といったら動的計画法?最長共通部分列を扱う場合は動的計画法、と刷り込まれているので、この問題もまずは動的計画法で書いてみました。なるように値を埋めていきます。j)の部分列でもある。s[i]とt[j]の前までが部分列になっていて、s[i]とt[j]が同じ文字の場合もOK。アルゴリズム自体は正しいと思うのですが、このコードを提出しても制限時間超過で受け付けてもらえません。いうコメントがある箇所で、sがtの部分文字列でないと早々にわかった場合は早めにfalseを返すコードを入れて少しでも実行時間を短くしようとしてみましたが、それでもだめでした。Pointers実はsがtの部分列かどうかを判定するだけなら、動的計画法を使用する必要はありません。sとtの文字列を先頭から順に操作するポインタiとjを定義しておき、同じ文字が現れる箇所をチェックしながらポインタを進めていけばOKです。0からスタートですが、文字s[0]が文字列tに出現するかどうかチェックします。出現するならその位置までjを進め、最後までs[0]が出現しなければsはtの部分列ではありません。これを、iも0から順に増やして最後まで回します。説明下手なので、さっそくコードを見てください。空間計算量O(1)なので動的計画法を使用した方法より高速で、テストケースも全てパスします。アーカイブおすすめの本はてなブログをはじめよう!kanohkさんは、はてなブログを使っています。ブログを報告するスターをつけました引用をストックしましたストック一覧を見る閉じる引用するにはまずログインしてくださいログイン閉じる引用をストックできませんでした。再度お試しください閉じる限定公開記事のため引用できません。