どーも！
たかぽんです！
今日もやっていきます！
392. Is Subsequence
本日は以下の問題です！
問題は、二つ文字列が与えられ、一方の文字列の文字がもう一方に含まれており、なおかつ、その順序は保たれているかどうか・・・・を判定するプログラムです。
言葉では難しいので例を...
以下、引用したものですが、sはtの文字列のSubsequenceと言えます。
Input: s = "abc", t = "ahbgdc"
Output: trueつまり、"ahbgdc"という文字列から、一部(hgd)を抜きだすと、"abc"になります。
このように、順序を変えずに一部だけ取り除いた文字列をオリジナル文字列のサブシークエンスと呼ぶようです。（初めて知った...!）
そのサブシークエンスになっているかどうかを調べろってことですね！
では、次章でアルゴリズムを検討してみようと思います...!
アルゴリズム
最初ずっと路頭に迷いました...
今回、サブシークエンスの文字列はsとして渡されています。
その文字列から、先頭を一つづつ見ていき、左から探します。
探して、見つかったら、その見つかった文字以降の残りの文字だけ取得し、そこの中からサブシークエンスの次の文字があるかどうかを探します。
こうすることで、サブシークエンスの左から一つづつさがし、なおかつオリジナルの順序が正しいことがわかりそうです。
もしもサブシークエンスの文字列が逆順等になっていたら、早い段階で本来含まれるべきあたいがスライスで消されてしまうため、ちゃんと整合性も保った状態を維持できるわけですね！
先程の例で試しておきます...!
手順イメージは以下のような形です。
Input: s = "abc", t = "ahbgdc"
sの左からaを取得
tからaを探す。(なければサブシークエンスではない）
aがあったため、残りの"hbgdc"をtに置き換え(aから手前は切り捨てる)
Input: s = "abc", t = "hbgdc"
sの次の要素をみる。
bなので、tからbを探す。(なければサブシークエンスではない）
存在したため、それ以降の文字列"gdc"をtに置き換え(bから手前は切り捨てる）
Input: s = "abc", t = "gdc"
sの最後の要素をみる。
cなので、tからcを探す。(なければサブシークエンスではない）
存在したため、それ以降の文字列""をtに置き換え(cから手前は切り捨てる）
sを全て見終えたので、for分を抜ける
無事抜けた場合はサブシークエンス。上記をコードに直したものを次章に置いておきます。
提出したコード
class Solution:
def isSubsequence(self, s: str, t: str) -> bool:
for char in s:
i = t.find(char)
if i == -1:
return False
else:
t = t[i+1:]
return True
## 結果
Runtime: 28 ms, faster than 89.11% of Python3 online submissions for Is Subsequence.
Memory Usage: 14.3 MB, less than 79.02% of Python3 online submissions for Is Subsequence.