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?

引用元：　https://leetcode.com/problems/is-subsequence/
　　
ざっくりと翻訳すると、
「文字列sは、文字列tに順番を変えずに存在していますか？」
です。

他の人の回答例（正解ではない）

他の人の回答の「分析」と「改善案」と「気づき」。

ruby

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

「is_subsequence」というメソッドを定義。
第一仮引数＝「s」、第二仮引数＝「t」と定義する。

2. メソッドの処理

ruby

  return true if s.empty? && t.empty?
  

初っ端に

「もし、sとtが空であったら本ステップで処理終了」

という開幕直後の唐突処理😳

参考：https://docs.ruby-lang.org/ja/latest/method/String/i/empty=3f.html

ruby

    
  s_idx = 0
  t_idx = 0

   

「s_idx」 と 「t_idx」 に対して「0」を代入する。
idxということで、s、ｔの文字を後に配列のように扱う際に、添字とするという思想があるのだろう（配列にはしていない）。
以後while文内で使用。

ruby

  s_len = s.length
  t_len = t.length

「s_len」 に対し 「s.length」、 「t_len」 に対し 「t.length」を代入する。
これによって「s」、「t」の 文字数 が共に定義される。
以後while文内として使用。

ruby

   while(t_idx < t_len)

         〜省略ー

   end

「tの添字 < tの文字数」の条件のあいだは繰り返しの処理を行う。

↓以下、while文の中身（処理）

ruby

#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の文字数が等しければここで処理を返す。

ステップ③　

　②で処理が返らなければ、更にもう一度①から処理を繰り返す。

ruby

  false

もし、①、②、③の全てのループを完走してしまったら、最後は上記「false」を処理の値として返却する。