Use a recursive solution

1 files changed, 21 insertions, 0 deletions

diff --git a/misc/subsequence/main.rb b/misc/subsequence/main.rb
index 7a9c980..e8e2341 100644
--- a/misc/subsequence/main.rb
+++ b/misc/subsequence/main.rb
@@ -253,6 +253,27 @@ class Solution
 
     result
   end
+
+  def self.run(sequence, pattern, index = 0)
+    puts [sequence, pattern, index].inspect if ENV['DEBUG']
+    return index if pattern.nil? || pattern.empty?
+    return index if sequence.nil? || sequence.empty?
+
+    case (atom = pattern[0])
+    when '*'
+      if sequence[1] == pattern[1]
+        run(sequence[1..-1], pattern[1..-1], index)
+      else
+        run(sequence[1..-1], pattern, index)
+      end
+    else
+      if sequence[0] == atom
+        run(sequence[1..-1], pattern[1..-1], index)
+      else
+        run(sequence[1..-1], pattern, index + 1)
+      end
+    end
+  end
 end
 
 assert_equal 0, Solution.run('abcdef', 'a*d*f')