はじめに
LeetCodeの問題を解答します。
なるべく、問題の和訳と詳細なコメントを書いています。
余裕があれば、複数のアプローチの解答と、実際の面接を想定して英語での解法やコメントを書いています。
様々なカテゴリの問題をランダムにあたる方法も良いですが、
二分探索、連結リストなど、テーマを絞って集中的に解いた方が練習しやすい方は以下の記事が有用です。
テーマごとに問題を分類しました。
LeeetCodeの問題をアルゴリズムとデータ構造による分類しました。
また、LeetCodeではAtcoderと違ってクラスと関数を定義して解答します。
LeetCodeに特有の内容など、知っておくと役に立つかもしれないことをまとめています。
はじめてLeetCodeに触れる方はこちらの記事も役に立つと思います。
ポイント
-
- two pointer
詳細
問題
原文
Given two strings
sandt, returntrueifsis a subsequence oft, orfalseotherwise.A subsequence of a string is a new string that is formed from the original string by deleting some (can be none) of the characters without disturbing the relative positions of the remaining characters. (i.e.,
"ace"is a subsequence of"abcde"while"aec"is not).
Example 1:
Example 2:
Constraints:
0 <= s.length <= 1000 <= t.length <= 104sandtconsist only of lowercase English letters.
Follow up: Suppose there are lots of incoming
s, says1, s2, ..., skwherek >= 109, and you want to check one by one to see ifthas its subsequence. In this scenario, how would you change your code?
内容(和訳)
二つの文字列sとtが与えられた場合、sがtの部分列であればtrueを返し、そうでなければfalseを返します。
文字列の部分列とは、元の文字列からいくつかの文字（なくても構いません）を削除しても、残りの文字の相対的な位置を変えずに形成される新しい文字列のことを指します（つまり、「ace」は「abcde」の部分列であり、「aec」は部分列ではありません）。
※chatGPTによる翻訳
解答
解答1：Python, two pointer
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
class Solution: def isSubsequence(self, s: str, t: str) -> bool: #s,tのそれぞれにポインタを用意 pointer_s = pointer_t = 0 #s,tのどちらかのポインタが終端に到着するまで繰り返す while pointer_s < len(s) and pointer_t < len(t): #それぞれのポインタが示すsとtの文字が一致した場合 if s[pointer_s] == t[pointer_t]: #sのポインタを進める pointer_s += 1 #tのポインタは各ループで必ず進める pointer_t += 1 #sのポインタが最後まで到達していたらTrueを返す。 if pointer_s == len(s): return True else: False |
終わりに
補足・参考・感想
問題を分類しました。テーマごとに集中して問題を解くことができます。
LeeetCodeの問題をアルゴリズムとデータ構造による分類
LeetCodeに特有の内容など、知っておくと役に立つかもしれないことをまとめました。
疑問が解決した方は他の問題もどうぞ
前：151. Reverse Words in a String
次：643. Maximum Average Subarray I
コメント