leetcode#10. Regular Expression Matching

本文主要是介绍leetcode#10. 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

理解

.匹配任意字符，*重复前一个字符0次或任意次
题目理解起来简单，处理起来很麻烦。初步的想法就是递归处理，但是我在递归时犯了个小错误，一边递归一边在while循环，这样很容易造成边界问题，特别的烦人，总是这个if处理好了，另一个if就会造成问题，没有办法统一各种情况。去网上查了下答案，简单的貌似都是DP思路，另一些就是用递归+if来处理。这题搞了得有5，6个小时，一大半的时间都浪费在了错误的递归，拆东墙补西墙上。看了答案发现和我之前思路一样后，还是定下心来，把原来的代码废弃了，重写了个 递归，代码如下：

class Solution(object):def isMatch(self, s, p):""":type s: str:type p: str:rtype: bool"""if p == s:return Trueif p == "" or (p != '' and p[0] == '*'):#s!=p && p == ""肯定错；格式问题，第一个为*肯定错return Falseif s == "":#处理s为空的情况if len(p) >= 2 and p[1] == '*':return self.isMatch(s, p[2:])else:return False#下面两个if为加速生成运算结果，没有也不会错，但可能会超时if s[-1] != p[-1] and p[-1] != '.' and p[-1] != '*':#s，p最后一位不相等，肯定错return Falseif p[-1] == "*":if p[-2] != s[-1] and p[-2] != '.':#可以访问p[-2]，因为p只是*的情况前面已经排除了return self.isMatch(s, p[:-2])#不考虑后两位elif p[-2] == s[-1] or p[-2] == '.':return self.isMatch(s[:-1], p) or self.isMatch(s, p[:-2])#第一种是s="aaa" p="a*"情况，第二种是s="a" p="aa*"slen = len(s)plen = len(p)if p[0] == s[0] or p[0] == '.':if plen > 1:if p[1] == "*":#匹配第一个，且p[1] = *for j in range(slen + 1):prefix = ""for k in range(j):#将p[0]重复0到slen次，判断期间有没有匹配成功prefix += p[0]if self.isMatch(s, prefix + p[2:]) == True:return Truereturn self.isMatch(s[1:], p[1:])#继续递归匹配后续字符串else:if plen > 1:if p[1] == "*":#第一个字符不相等，但是p[1] = *，则忽略p前两位return self.isMatch(s, p[2:])return False#剩下情况都为错

注释已经基本解释清了

总结

写递归的时候，一定要避免写循环，不然边界太难控制了啊

附

提供几个测试用例

"a"
"..*""aaa"
"aaaa""aa"
"a""aa"
"a*""bbbba"
".*a*a""aaaaaaab"
"a*a*a*a*a*a*a*a*b"

这篇关于leetcode#10. Regular Expression Matching的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---