ゼロから始めるLeetCode Day82「392. Is Subsequence」

概要

海外ではエンジニアの面接においてコーディングテストというものが行われるらしく、多くの場合、特定の関数やクラスをお題に沿って実装するという物がメインである。

どうやら多くのエンジニアはその対策としてLeetCodeなるサイトで対策を行うようだ。

早い話が本場でも行われているようなコーディングテストに耐えうるようなアルゴリズム力を鍛えるサイトであり、海外のテックカンパニーでのキャリアを積みたい方にとっては避けては通れない道である。

と、仰々しく書いてみましたが、私は今のところそういった面接を受ける予定はありません。

ただ、ITエンジニアとして人並みのアルゴリズム力くらいは持っておいた方がいいだろうということで不定期に問題を解いてその時に考えたやり方をメモ的に書いていこうかと思います。

Leetcode

Python3で解いています。

ゼロから始めるLeetCode 目次

前回
ゼロから始めるLeetCode Day81 「347. Top K Frequent Elements」

次回
ゼロから始めるLeetCode Day83 「102. Binary Tree Level Order Traversal」

Twitterやってます。

問題

392. Is Subsequence
難易度はEasy。

前回と同様問題集からの抜粋です。

問題としては、文字列sと文字列tが与えられたとき,sがtの部分連続であるかどうかを調べよ、というものです。

なお、ここでの文字列の部分連続とは、元の文字列から、残りの文字の相対的な位置を崩さずに、文字の一部を削除することによって形成される新しい文字列のことです(何もなくてもよい)。(例えば、"ace "は "abcde "の部分文字列ですが、"aec "はそうではありません)。

Example 1:

Input: s = “abc”, t = “ahbgdc”
Output: true

Example 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.

pointerを二つ使って考える形式を取りました。

仮にspreインデックスがtのcurインデックス、すなわち部分文字列が見つかった時にpreの値を増加させ、それ以外の時はcur側の値を増加させることで、tのインデックスをずらすことができます。これをprecurそれぞれがstの長さ未満の間続けることで、仮にpreの値がsの長さと一致しない場合はFalseを、それ以外の場合はTrueを返すようにしています。

何のアルゴリズムというわけではありませんが、総合的に考える問題とあった通り、いろんなやり方があると思いますが、今回はこんな感じになりました。

では今回はここまで。お疲れ様でした。

コメント

このブログの人気の投稿

Braveブラウザの同期機能をiPhoneで設定した話。

自作のChrome Extensionをインポートした時に "Invalid value for 'content_scripts[0].matches[0]': Empty path."というエラーが出たので解決した

failed: unable to get local issuer certificate (_ssl.c:1123)と出たので解決した話