Commit 4f53805

@@ -7,11 +7,6 @@ def assert_equal(x, y)
 end
 
 =begin
-time: O(n)
-space: O(1)
-
-wildcard = false
-
  x
 |a|b|c|d|e|f|
 
@@ -90,7 +85,6 @@ class Solution
       self.next.match?(input)
     end
 
-
     def to_s
       self.class.to_s
     end
@@ -197,14 +191,76 @@ class Solution
     machine = build_machine(pattern)
     machine.parse(sequence)
   end
+
+  def self.state_for(token)
+    return :final if token.nil?
+
+    case token
+    when '*'
+      :wildcard
+    else
+      :literal
+    end
+  end
+
+  def self.debug(state, sequence_pos, pattern_pos, sequence, pattern)
+    return unless ENV['DEBUG']
+
+    puts [state].inspect
+    puts "  " + (" " * sequence_pos) + "v"
+    puts "  " + sequence
+    puts "  " + (" " * pattern_pos) + "v"
+    puts "  " + pattern
+  end
+
+  # start, literal, wildcard, final
+  def self.run(sequence, pattern)
+    state = :start
+    sequence_pos = 0
+    pattern_pos = 0
+    result = nil
+
+    while pattern_pos < pattern.size && sequence_pos < sequence.size
+      debug(state, sequence_pos, pattern_pos, sequence, pattern)
+
+      case state
+      when :start
+        pattern_pos = 0
+        result = sequence_pos
+        state = state_for(pattern[pattern_pos])
+      when :literal
+        if sequence[sequence_pos] == pattern[pattern_pos]
+          pattern_pos += 1
+          state = state_for(pattern[pattern_pos])
+        else
+          state = :start
+          result = nil
+        end
+
+        sequence_pos += 1
+      when :wildcard
+        lookahead = pattern[pattern_pos + 1]
+        if sequence[sequence_pos] == lookahead
+          state = state_for(lookahead)
+          pattern_pos += 1
+        else
+          sequence_pos += 1
+        end
+      when :final
+        break
+      end
+    end
+
+    result
+  end
 end
 
 assert_equal 0, Solution.run('abcdef', 'a*d*f')
-assert_equal 1, Solution.run('abcddef', 'bc*de')
-assert_equal 1, Solution.run('abcd', 'b*d')
-assert_equal 2, Solution.run('abacd', 'ac*')
 assert_equal 0, Solution.run('abcdefg', 'a*d*f')
-assert_equal 3, Solution.run('xyzabcdef', 'a*d*f')
 assert_equal 0, Solution.run('abcdefxyz', 'a*d*f')
 assert_equal 0, Solution.run('mo is the best', 'm* is the ****')
+assert_equal 1, Solution.run('abcd', 'b*d')
+assert_equal 1, Solution.run('abcddef', 'bc*de')
+assert_equal 2, Solution.run('abacd', 'ac*')
+assert_equal 3, Solution.run('xyzabcdef', 'a*d*f')
 assert_equal 7, Solution.run('Phone: +1(403)-555-5555', '+*(***)-***-****')