[LeetCode][Python]Regular Expression Matching
# -*- 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
如果匹配，
不带*，递归s,p
带*，考虑匹配0到最远端的情况，分别递归s,p
'''
class Solution:
# @return a boolean
def isMatch(self, s, p):
def compress(p):
i = 0
while i < len(p)-3:
if p != '*':
i = i + 1
continue
if p == '*':
if p == "." or p == ".":
p = p[:i] + ".*" + p
continue
elif p == p:
p = p[:i] + p
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
multi = False
if len(p) > 1:
if p == "*":
multi = True
if match_char != s and match_char != ".":
if multi:
return isMatch2(s, p)
else:
return False
if multi is False:
return isMatch2(s, p)
else:
result = False
i = 0
result = isMatch2(s, p)
while i < len(s):
if result == True:
return result
if (s == match_char or match_char == "."):
result = isMatch2(s, p)
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)
页:
[1]