class Solution1:
	# @param s, a string
	# @param p, a string
	# @return a boolean
	def isMatch(self, s, p):
		i = 0
		tempP = ""
		prev = ""
		while i < len(p):
			if i < len(p) - 1:
				if len(prev) == 0:
					if  p[i+1] == "*":
						prev = p[i] + '*'
						tempP += p[i] + '*'
						i_inc = 2
					else:
						prev = p[i]
						tempP += p[i]
						i_inc = 1
				elif p[i] != prev[0] and p[i+1] == "*":
					prev = p[i] + '*'
					tempP += p[i] + '*'
					i_inc = 2
				elif  p[i] == prev[0] and len(prev) > 1 and prev[1] == "*" and p[i+1] == "*":
					i_inc = 2
				elif p[i] == prev[0] and len(prev) == 1 and p[i+1] == "*":
					prev = p[i] + '*'
					tempP += p[i] + '*'
					i_inc = 2
				elif p[i+1] != '*':
					prev = p[i]
					tempP += p[i]
					i_inc = 1
			elif i == len(p) -1:
				tempP += p[i]
				break
			i += i_inc
		return self.matchAfterClean(s, tempP)


	def matchAfterClean(self, s, p):
		if len(p) == 0 and len(s) == 0:
			return True
		elif len(s) == 0:
			if len(p) > 1 and p[1] == '*':
				return self.matchAfterClean(s, p[2:len(p)])
			else:
				return False
		elif len(p) == 0:
			return False

		reg = p[0]
		# '.' or not
		if reg == '.':
			anyone = True
		else:
			anyone = False

		# '*' or not
		if len(p)>1 and p[1] == '*':
			zeroOrMulti = True
		else:
			zeroOrMulti = False


		if reg == s[0]:
			if not zeroOrMulti:
				return self.matchAfterClean(s[1:len(s)], p[1:len(p)])
			else:
				return self.matchAfterClean(s[1:len(s)], p) or self.matchAfterClean(s, p[2:len(p)])
		else:
			if anyone and not zeroOrMulti:
				return self.matchAfterClean(s[1:len(s)], p[1:len(p)])
			elif anyone and zeroOrMulti:
				return self.matchAfterClean(s[1:len(s)], p) or self.matchAfterClean(s, p[2:len(p)])
			elif not anyone and zeroOrMulti:
				return self.matchAfterClean(s, p[2:len(p)])
			else:
				return False