ゼロから始めるLeetCode Day82「392. Is Subsequence」
概要
海外ではエンジニアの面接においてコーディングテストというものが行われるらしく、多くの場合、特定の関数やクラスをお題に沿って実装するという物がメインである。
どうやら多くのエンジニアはその対策としてLeetCodeなるサイトで対策を行うようだ。
早い話が本場でも行われているようなコーディングテストに耐えうるようなアルゴリズム力を鍛えるサイトであり、海外のテックカンパニーでのキャリアを積みたい方にとっては避けては通れない道である。
と、仰々しく書いてみましたが、私は今のところそういった面接を受ける予定はありません。
ただ、ITエンジニアとして人並みのアルゴリズム力くらいは持っておいた方がいいだろうということで不定期に問題を解いてその時に考えたやり方をメモ的に書いていこうかと思います。
Python3で解いています。
前回
ゼロから始めるLeetCode Day81 「347. Top K Frequent Elements」
Twitterやってます。
技術ブログ始めました!!
技術はLeetCode、Django、Nuxt、あたりについて書くと思います。こちらの方が更新は早いので、よければブクマよろしくお願いいたします!
問題
392. Is Subsequence
難易度はEasy。
前回と同様問題集からの抜粋です。
問題としては、文字列sと文字列tが与えられたとき,sがtの部分連続であるかどうかを調べよ、というものです。
なお、ここでの文字列の部分連続とは、元の文字列から、残りの文字の相対的な位置を崩さずに、文字の一部を削除することによって形成される新しい文字列のことです(何もなくてもよい)。(例えば、"ace "は "abcde "の部分文字列ですが、"aec "はそうではありません)。
Example 1:
Input: s = "abc", t = "ahbgdc"
Output: trueExample 2:
Input: s = "axc", t = "ahbgdc"
Output: false
解法
class Solution:
def isSubsequence(self, s: str, t: str) -> bool:
pre = cur = 0
while pre < len(s) and cur < len(t):
if s[pre] == t[cur]:
pre +=1
cur +=1
return pre == len(s)
# Runtime: 36 ms, faster than 60.46% of Python3 online submissions for Is Subsequence.
# Memory Usage: 14.1 MB, less than 35.95% of Python3 online submissions for Is Subsequence.
class Solution:
def isSubsequence(self, s: str, t: str) -> bool:
pre = cur = 0
while pre < len(s) and cur < len(t):
if s[pre] == t[cur]:
pre +=1
cur +=1
return pre == len(s)
# Runtime: 36 ms, faster than 60.46% of Python3 online submissions for Is Subsequence.
# Memory Usage: 14.1 MB, less than 35.95% of Python3 online submissions for Is Subsequence.
pointerを二つ使って考える形式を取りました。
仮にs
のpre
インデックスがtのcur
インデックス、すなわち部分文字列が見つかった時にpre
の値を増加させ、それ以外の時はcur
側の値を増加させることで、t
のインデックスをずらすことができます。これをpre
とcur
それぞれがs
とt
の長さ未満の間続けることで、仮にpre
の値がs
の長さと一致しない場合はFalse
を、それ以外の場合はTrue
を返すようにしています。
何のアルゴリズムというわけではありませんが、総合的に考える問題とあった通り、いろんなやり方があると思いますが、今回はこんな感じになりました。
では今回はここまで。お疲れ様でした。
Author And Source
この問題について(ゼロから始めるLeetCode Day82「392. Is Subsequence」), 我々は、より多くの情報をここで見つけました https://qiita.com/KueharX/items/ddf57a3f819e70f7e61f著者帰属:元の著者の情報は、元のURLに含まれています。著作権は原作者に属する。
Content is automatically searched and collected through network algorithms . If there is a violation . Please contact us . We will adjust (correct author information ,or delete content ) as soon as possible .