Leetcode(10) Regular Expression Matching

发表于 | 更新于 | 分类于

Description:

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

解法：

此题的关键在于对‘’号的处理，因为不知道到底会匹配多少个字符，但是有一点，‘’不会单独出现，它一定是和前面一个字母或”.”配成一对。看成一对”X*”，它的性质就是：要不匹配0个，要不匹配连续的“X”，关键在于匹配正确个数的字符。

考虑一个特殊的问题：
情况1：
“aaaaaaaaaaaaaaaa”
“aaa”

情况2：
“aaaaaaaaaaaaaaaa”
“aab”

最长匹配？
显然不合适，这样后面的a就无法匹配上了

匹配到和后面长度一样的位置，比如情况1，就是留3个a不匹配，让后面3个字母尝试去匹配？
这样看似合适，但是遇到情况2就不行了。

回溯，每种匹配个数的情况，看哪种情况能成功，如果其中出现了问题，马上回溯，换下一种情况

因此，采用递归的方法解决该问题，用p去与s做匹配（即代码中判定以p为准），实际上也是深度优先搜索，对该问题的分解如下：

递归出口：

若p为空，对s而言：

若s也为空，返回true，反之返回false

若p的长度为1，对s而言：

若此时若s长度也为1，且s与p相同或是p为’.’，则返回true，反之返回false

递归体：

考虑该问题还未进行最小划分的情况，即此时p的长度大于1，对两串从左至右进行匹配。

情况1：若此时 p[1] !=’*’

1.1 如果s的长度为0，匹配失败，则返回false

1.2如果s[0] == p[0] 或 p[0] == ‘*’，匹配暂时成功，递归看看s与p的头指针向右移一位之后的串匹配是否成功

1.3否则匹配失败，返回false

情况2：此时的 p[1] == ‘*’

2.1当s的长度不为0且s[0] == p[0] 或 p[0] == ‘’时，暂时地匹配成功了，将s的头指针右移一位，进入下一次循环判断，值得注意的是，当匹配至p中’’后的串与此时遗留的s串相匹配时，不需要进行进一步的匹配了，两串完全匹配成功，返回true。

2.2剩下的情况即，s[0] != p[0] 且 p[0] ！= ‘’，则考虑此时X组合匹配0次，递归看看p中’*’后的串与此时遗留的s串是否匹配

我的代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution:
    def isMatch(self, s, p):
        """
        :type s: str
        :type p: str
        :rtype: bool
        """
        if(len(p) == 0):
            if(len(s) == 0):
                return True;
            return False;
        if(len(p) == 1):
            if(len(s) == 1):
                if(p[0] == '.' or s[0] == p[0]):
                    return True;
            return False;
        if(p[1] != '*'):
            if(len(s) == 0):
                return False;
            if(p[0] == s[0] or p[0] == '.'):
                return Solution.isMatch(Solution,s[1:],p[1:]);
            return False;
        #p[1] == '*'的情况
        while(len(s)!=0 and (s[0] == p[0] or p[0] == '.')):
            if(Solution.isMatch(Solution,s,p[2:])):
                return True;
            l = list(s[1:]);
            s = "".join(l);
        return Solution.isMatch(Solution,s,p[2:]);