subsequence problem

2 files changed, 60 insertions, 0 deletions

diff --git a/misc/subsequence/README.md b/misc/subsequence/README.md
new file mode 100644
index 0000000..b51380b
--- /dev/null
+++ b/misc/subsequence/README.md
@@ -0,0 +1,10 @@
+
+Given a string,
+find the index of a substring with a wildcard, `*`,
+meaning zero or more characters
+
+inputs:
+
+```plaintext
+match(abcdef, a*d*f) => 0
+```
diff --git a/misc/subsequence/main.rb b/misc/subsequence/main.rb
new file mode 100644
index 0000000..9c62a77
--- /dev/null
+++ b/misc/subsequence/main.rb
@@ -0,0 +1,50 @@
+def assert_equal(x, y)
+  raise [x, y].inspect unless x == y
+end
+
+=begin
+ w = false
+
+           x
+|a|b|c|d|e|f|
+
+           y
+|a|*|d|*|f|
+=end
+
+class Solution
+  def self.run(sequence, pattern)
+    p = 0
+    index = nil
+
+    0.upto(sequence.length - 1) do |n|
+      x = sequence[n]
+      y = pattern[p]
+
+      if y == '*'
+        index = n if p.zero?
+        l = pattern[p + 1]
+
+        p += 2 if l == x
+      elsif x == y
+        index = n if p.zero?
+
+        p += 1
+      else
+        index = nil
+        p = 0
+      end
+    end
+
+    index
+  end
+end
+
+assert_equal 0, Solution.run('abcdef', 'a*d*f')
+assert_equal nil, Solution.run('abcdefg', 'a*d*f')
+assert_equal 3, Solution.run('xyzabcdef', 'a*d*f')
+assert_equal nil, Solution.run('abcdefxyz', 'a*d*f')
+assert_equal 0, Solution.run('mo is the best', 'm* is the ****')
+assert_equal 7, Solution.run('Phone: +1(403)-555-5555', '+*(***)-***-****')
+
+puts "YAY!"