Skip to content

Instantly share code, notes, and snippets.

@MarkLavrynenko
Created June 29, 2015 13:54
Show Gist options
  • Save MarkLavrynenko/38c9cb42e990d459b0a9 to your computer and use it in GitHub Desktop.
Save MarkLavrynenko/38c9cb42e990d459b0a9 to your computer and use it in GitHub Desktop.
Tiny regex matcher
import string
class Node:
def __init__(self):
self._links = {}
self._is_finite = False
def set_link(self, letter, node):
if letter == '.':
for l in string.lowercase[:26]:
self.set_link(l, node)
if self._links.get(letter) is None:
self._links[letter] = [node]
else:
self._links[letter].append(node)
def get_links(self, letter):
return self._links.get(letter)
def set_loop(self, letter):
self.set_link(letter, self)
def set_finite(self):
self._is_finite = True
def is_finite(self):
return self._is_finite
def __repr__(self):
return "FSM Node (_links = %s, _is_finite = %s)" % (self._links, self._is_finite)
class Automata:
def __init__(self, pattern):
self._root = Node()
# parse pattern
groups = []
for char in pattern:
if char == '*':
n = len(groups)
groups[n-1]['repeatale'] = True
else:
group = {
'letter' : char,
'repeatale' : False
}
groups.append(group)
last = self._root
# build FSM
for group in groups:
if group['repeatale'] == False:
node = Node()
last.set_link(group['letter'], node)
last = node
else:
last.set_loop(group['letter'])
last.set_finite()
print "FSM is build"
def match(self, str):
positions = [self._root]
chars_count = len(str)
for char_index, char in enumerate(str):
next_positions = []
for node in positions:
nodes = node.get_links(char);
if nodes is None:
continue
for node in nodes:
if (char_index == chars_count -1 and node.is_finite()):
return True
next_positions.append(node)
positions = next_positions
return False
class Solution:
# @param {string} s
# @param {string} p
# @return {boolean}
def isMatch(self, s, p):
automata = Automata(p)
return automata.match(s)
def test():
sol = Solution()
assert sol.isMatch("abba", "ab*a") == True
assert sol.isMatch("aa","a") == False
assert sol.isMatch("aa","aa") == True
assert sol.isMatch("aaa","aa") == False
assert sol.isMatch("aa", "a*") == True
assert sol.isMatch("aa", ".*") == True
assert sol.isMatch("ab", ".*") == True
assert sol.isMatch("aab", "c*a*b") == True
test()
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment