MarkLavrynenko · June 29, 2015 13:54 · Jun 29, 2015
diff --git a/gistfile1.py b/gistfile1.py
@@ -0,0 +1,97 @@
+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()