Is Subsequence 〜leetcode〜
〜問題文〜
Given two strings s and t, check if s is a subsequence of t.
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:
Input: s = "abc", t = "ahbgdc"
Output: true
Example 2:
Input: s = "axc", t = "ahbgdc"
Output: false
Constraints:
0 <= s.length <= 100
0 <= t.length <= 104
s and t consist only of lowercase English letters.
Follow up: If there are lots of incoming s, say s1, s2, ..., sk where k >= 109, and you want to check one by one to see if t has its subsequence. In this scenario, how would you change your code?
Given two strings s and t, check if s is a subsequence of t.
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:
Input: s = "abc", t = "ahbgdc"
Output: true
Example 2:
Input: s = "axc", t = "ahbgdc"
Output: false
Constraints:
0 <= s.length <= 100
0 <= t.length <= 104
s and t consist only of lowercase English letters.
Follow up: If there are lots of incoming s, say s1, s2, ..., sk where k >= 109, and you want to check one by one to see if t has its subsequence. In this scenario, how would you change your code?
引用元： https://leetcode.com/problems/is-subsequence/
ざっくりと翻訳すると、
「文字列sは、文字列tに順番を変えずに存在していますか？」
です。
他の人の回答例（正解ではない）
他の人の回答の「分析」と「改善案」と「気づき」。
def is_subsequence(s, t)
return true if s.empty? && t.empty?
s_idx = 0
t_idx = 0
s_len = s.length
t_len = t.length
while(t_idx < t_len)
s_idx += 1 if s[s_idx] == t[t_idx]
return true if s_idx == s_len
t_idx += 1
end
false
end
以下、上記回答の分解分析
1. メソッドの定義
ruby
def is_subsequence(s, t)
〜省略〜
end
def is_subsequence(s, t)
〜省略〜
end
「is_subsequence」というメソッドを定義。
第一仮引数＝「s」、第二仮引数＝「t」と定義する。
2. メソッドの処理
return true if s.empty? && t.empty?
初っ端に
「もし、sとtが空であったら本ステップで処理終了」
という開幕直後の唐突処理😳
参考：https://docs.ruby-lang.org/ja/latest/method/String/i/empty=3f.html
s_idx = 0
t_idx = 0
「s_idx」 と 「t_idx」 に対して「0」を代入する。
idxということで、s、ｔの文字を後に配列のように扱う際に、添字とするという思想があるのだろう（配列にはしていない）。
以後while文内で使用。
s_len = s.length
t_len = t.length
「s_len」 に対し 「s.length」、 「t_len」 に対し 「t.length」を代入する。
これによって「s」、「t」の 文字数 が共に定義される。
以後while文内として使用。
while(t_idx < t_len)
〜省略ー
end
「tの添字 < tの文字数」の条件のあいだは繰り返しの処理を行う。
↓以下、while文の中身（処理）
#while文内ステップ①
s_idx += 1 if s[s_idx] == t[t_idx]
#while文内ステップ②
return true if s_idx == s_len
#while文内ステップ③
t_idx += 1
ステップ①
もし、s[sの添字] == ｔ[tの添字]が等しかったら、自己代入演算子にて「s」に対して「+1」してあげる。
（sの添字（s_idx）は、0スタートだから。）
？ ？ ？
↑おそらくここがおかしい部分😎
sとtは現状、文字列のままである。
しかし、本ステップでは、配列と同じ振る舞い方をさせようとしている（添字idxをつけている）。
改善案として、while文の外で配列にする。
（例）s="abcd" → s = [a,b,c,d]
ステップ②
sの添字とsの文字数が等しければここで処理を返す。
ステップ③
②で処理が返らなければ、更にもう一度①から処理を繰り返す。
false
もし、①、②、③の全てのループを完走してしまったら、最後は上記「false」を処理の値として返却する。
Author And Source
この問題について(Is Subsequence 〜leetcode〜), 我々は、より多くの情報をここで見つけました https://qiita.com/Tech_geologist/items/82010ec4316b9e90a73a著者帰属：元の著者の情報は、元の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 .