[LeetCode][Python]Regular Expression Matching

ycvodzf

# -*- coding: utf8 -*-
'''
https://oj.leetcode.com/problems/regular-expression-matching/
Implement regular expression matching with support for '.' and '*'.
'.' Matches any single character.
'*' Matches zero or more of the preceding element.
The matching should cover the entire input string (not partial).
The function prototype should be:
bool isMatch(const char *s, const char *p)
Some examples:
isMatch("aa","a") → false
isMatch("aa","aa") → true
isMatch("aaa","aa") → false
isMatch("aa", "a*") → true
isMatch("aa", ".*") → true
isMatch("ab", ".*") → true
isMatch("aab", "c*a*b") → true
===Comments by Dabay===
自我感觉很解得很垃圾啊。如果不是把p做了压缩还过不了online judge。其实就是一个DFA。
当s和p都是空的时候，匹配成功。
如果s为空，p不为空，检查p的偶数为是不是都是*。
如果s和p都不为空，头一个字母
    如果不匹配，
        不带*，False
        带*，递归p[2:]
    如果匹配，
        不带*，递归s[1:],p[1:]
        带*，考虑匹配0到最远端的情况，分别递归s[i:],p[2:]
'''
class Solution:
    # @return a boolean
    def isMatch(self, s, p):
        def compress(p):
            i = 0
            while i < len(p)-3:
                if p[i+1] != '*':
                    i = i + 1
                    continue
                if p[i+3] == '*':
                    if p == "." or p[i+2] == ".":
                        p = p[:i] + ".*" + p[i+4:]
                        continue
                    elif p == p[i+2]:
                        p = p[:i] + p[i+2:]
                        continue
                i = i + 2
            return p
        def isMatch2(s, p):
            if len(s) == 0:
                if len(p) == 0:
                    return True
                if len(p) % 2 == 0:
                    i = 1
                    while i < len(p):
                        if p != "*":
                            return False
                        i = i + 2
                    else:
                        return True
                else:
                    return False
            if len(s) > 0 and len(p) == 0:
                return False
            match_char = p[0]
            multi = False
            if len(p) > 1:
                if p[1] == "*":
                    multi = True
            if match_char != s[0] and match_char != ".":
                if multi:
                    return isMatch2(s, p[2:])
                else:
                    return False
            if multi is False:
                return isMatch2(s[1:], p[1:])
            else:
                result = False
                i = 0
                result = isMatch2(s, p[2:])
                while i < len(s):
                    if result == True:
                        return result
                    if (s == match_char or match_char == "."):
                        result = isMatch2(s[i+1:], p[2:])
                    else:
                        break
                    i = i + 1
                return result
        return isMatch2(s, compress(p))

def main():
    s = Solution()
    print s.isMatch("aa", "a*")

if __name__ == "__main__":
    import time
    start = time.clock()
    main()
    print "%s sec" % (time.clock() - start)