From dbacfc1eaaec6de590c922591d35972c27a1b5f5 Mon Sep 17 00:00:00 2001
From: akmhmgc <akimuhamaguchi@icloud.com>
Date: Thu, 9 Oct 2025 22:09:34 +0900
Subject: [PATCH] 392

---
 392/step1.md | 55 +++++++++++++++++++++++++++++++++++++++++++
 392/step2.md | 66 ++++++++++++++++++++++++++++++++++++++++++++++++++++
 392/step3.md | 12 ++++++++++
 392/step4.md |  1 +
 4 files changed, 134 insertions(+)
 create mode 100644 392/step1.md
 create mode 100644 392/step2.md
 create mode 100644 392/step3.md
 create mode 100644 392/step4.md

diff --git a/392/step1.md b/392/step1.md
new file mode 100644
index 0000000..80c1092
--- /dev/null
+++ 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
new file mode 100644
index 0000000..71f53ad
--- /dev/null
+++ 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
new file mode 100644
index 0000000..62861cd
--- /dev/null
+++ 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
new file mode 100644
index 0000000..5941ee1
--- /dev/null
+++ b/392/step4.md
@@ -0,0 +1 @@
+## step4 レビューを受けて解答を修正