akmhmgc · akmhmgc · Oct 9, 2025 · tokuhirat · Oct 9, 2025 · potrue
diff --git a/392/step1.md b/392/step1.md
@@ -0,0 +1,55 @@
+# step1 何も見ずに解く
+sの文字の先頭をiとする。tを先頭から見ていき、iの文字があればi += 1に更新する。
+iが末尾までいけばsはtのsubsequenceと言える。
+tの長さをNとすると時間計算量はO(N)となる。
+空間計算量亜はO(1)
+Nの最大値が10^4なので1秒以内に間に合う。
+
+```ruby
+# @param {String} s
+# @param {String} t
+# @return {Boolean}
+def is_subsequence(s, t)
+    return true if s.size.zero?
+
+    last_subsequence_index = 0
+    t.each_char do |char|
+        last_subsequence_index += 1 if s[last_subsequence_index] == char
+        return true if last_subsequence_index == s.size
+    end
+    false
+end
+```
+
+Followupについて考える。
+今のコードだと、sがtに存在しない文字を含んでいてもtを最後まで見るので効率が悪い。
+tの文字をSetにしておいて存在しない文字を含んでいたらfalseを返すと、存在しない文字を前の方に含んでいるのを早めに弾けて速くなる可能性がある。
+
+```ruby
+# @param {List[String]} s_list
+# @param {String} t
+# @return {Boolean}
+def is_subsequence(strs, original_str)
+    original_str_set = Set.new
+    original_str.each_char do |char|
+      original_str_set << char
+    end
+
+    is_subsequence_helper = lambda do |str|
+      return true if str.size.zero?
+
+      last_subsequence_index = 0
+      original_str.each_char do |char|
+          return false unless original_str_set.include?(str[last_subsequence_index])
+          last_subsequence_index += 1 if str[last_subsequence_index] == char
+          return true if last_subsequence_index == str.size
+      end
+      false
+    end
+
+    strs.each_with_object({}) {|str, result| result[str] = is_subsequence_helper.call(str) }
+end
+
+is_subsequence(["abc", "ab", "zahbgdc"], "ahbgdc")
+# => {"abc"=>true, "ab"=>true, "zahbgdc"=>false}
+```
diff --git a/392/step2.md b/392/step2.md
@@ -0,0 +1,66 @@
+# step2 他の方の解答を見る
+## LCS
+https://github.com/shining-ai/leetcode/pull/57
+
+```ruby
+# @param {String} s
+# @param {String} t
+# @return {Boolean}
+def is_subsequence(s, t)
+    lcs_sizes = Array.new(s.size + 1) { Array.new(t.size + 1, 0) }
+    s.size.times do |i|
+        t.size.times do |j|
+            if s[i] == t[j]
+                lcs_sizes[i + 1][j + 1] = lcs_sizes[i][j] + 1
+            else
+                lcs_sizes[i + 1][j + 1] = [lcs_sizes[i + 1][j], lcs_sizes[i][j + 1]].max
+            end
+        end
+    end
+    lcs_sizes.last.last == s.size
+end
+```
+
+## 正規表現
+```ruby
+# @param {String} s
+# @param {String} t
+# @return {Boolean}
+def is_subsequence(s, t)
+  pattern = ""
+  s.each_char do |c|
+    pattern += ".*" + Regexp.escape(c)
+  end
+  t.match?(/^#{pattern}/)
+end
+```
+
+エスケープしておかないとReDos攻撃の危険があるので使うのは怖い。
+
+
+## Follow up
+tの文字とindexesのハッシュテーブル（char_to_indexesとする）を持っておいて、
+sに含まれる文字がtの中で前から順に含まれているかどうかをチェックしていけば良い。
+
+時間計算量はsの長さをMとするとO(M*logN)となる
+
+```ruby
+def is_subsequence(s, t)
+    return true if s.empty?
+
+    t_char_to_indexes = Hash.new { |h, k| h[k] = [] }
+    t.each_char.with_index { |ch, i| t_char_to_indexes[ch] << i }
+
+    last_matched_index = -1
+    s.each_char do |ch|
+        indexes = t_char_to_indexes[ch]
+        return false unless indexes
+
+        next_index = indexes.bsearch { |pos| pos > last_matched_index }
+        return false unless next_index
+
+        last_matched_index = next_index
+    end
+    true
+end
+```
diff --git a/392/step3.md b/392/step3.md
@@ -0,0 +1,12 @@
+# step3 3回続けて10分以内に書いてエラーを出さなければOKとする
+
+```ruby
+# @param {String} s
+# @param {String} t
+# @return {Boolean}
+def is_subsequence(s, t)
+    lcs_last_index = 0
+    t.each_char { |char| lcs_last_index += 1 if s[lcs_last_index] == char }
+    lcs_last_index == s.size
+end
+```
diff --git a/392/step4.md b/392/step4.md
@@ -0,0 +1 @@
+## step4 レビューを受けて解答を修正
Original file line number	Diff line number	Diff line change
		@@ -0,0 +1 @@
		## step4 レビューを受けて解答を修正