LeetCode#10 Implement regular ex

'.' Matches any single character.
'*' Matches zero or more of the preceding element.

The matching should cover the entire input string (not partial).

完成正则表达式.和*的功能
发现网上的答案有错。。。
看了solution的递归，第二个回去看一下DP再做

直接用正则。。。
import re 
class Solution(object):
    def isMatch(self, s, p):
        regex = re.compile('^'+p+'$')
        if regex.match(s):
            return True
        else:
            return False

这里面对p进行了处理：'^{'+p+'$'，其中'}'表示当前开始，'$'表示添补末尾空行，match是从第一个字符开始匹配，不存在返回None
答案中递归的思路是：从前向后依次匹配s[i:]和p[j:]，遇到'*'分两种情况处理：递归匹配s[i+1:]，p[j:]，或者s[i:],p[j+2:]。

class Solution(object):
    def isMatch(self, s, p):
        if not p:
            if not s:
                return True
                return False
        firstMatch = bool(s) and (p[0] ==s[0] or p[0] =='.')
        if len(p)>2 and p[1]=='*':
            return self.isMatch(s[0:],p[2:]) or (firstMatch and self.isMatch(s[1:],p[0:]))
        else:
            return firstMatch and self.isMatch(s[1:],p[1:])

思想比较好理解，但是在实现的时候，and前后的顺序包涵着判空（python 的and前如果为假就不会去执行后面的语句），顺序不能改变。

1. bool(s)这一个语句是判断s是否为空，避免后面越界
2. 第一个return，or前面的语句是任何时候都会成立的，因为if保证了p的最小下标，任意串都可以被访问s[0:]（包括空串），如果出现了s空，p非空的情况，每次递归时若都会执行第一个return，则每次递归时firstMatch均为假，并且一定会有s空，p空的情况出现，执行第二个return返回假，可能越界的s[1:]永远不会被执行。
3. 最开始的p,s 空串判断是很容易想到的结束条件。