【LeetCode】10. Regular Expression Matching

简易正则匹配…不坑，就是不太会(⊙﹏⊙)b

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

'.' 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

读题需注意： *可以一个都不匹配的。

然后关于题解的话，大致是这样的：

class Solution(object):
    def isMatchCal(self, s, i, p, j) :
        slen = len(s)
        plen = len(p)
        #如果s匹配结束了，说明p应该也匹配结束了或者后面都是匹配0个的...(类似 .*)
        if i == slen :
            return j == plen or (j+1 < plen and p[j+1] == '*' and self.isMatchCal(s, i, p, j+2))
        
        #当前匹配字符的下一个是*号...说明可能匹配多个
        if j+1 < plen and p[j+1] == '*' :
            if p[j] == '.' or p[j] == s[i] :
                return self.isMatchCal(s, i+1, p, j) or self.isMatchCal(s, i, p, j+2)
            else :
                return self.isMatchCal(s, i, p, j+2)
        #或者当前匹配字符的下一个不是*号，但是当前字符匹配成功，则继续匹配
        #如果不成功，说明出错了...
        else :
            if j < plen and (p[j] == '.' or p[j] == s[i]) :
                return self.isMatchCal(s, i+1, p, j+1)
            else :
                return False
        
        
    def isMatch(self, s, p):
        """
        :type s: str
        :type p: str
        :rtype: bool
        """
        return self.isMatchCal(s, 0, p, 0)

class Solution(object):

def isMatchCal(self, s, i, p, j) :

slen = len(s)

plen = len(p)

#如果s匹配结束了，说明p应该也匹配结束了或者后面都是匹配0个的...(类似 .*)

if i == slen :

return j == plen or (j+1 < plen and p[j+1] == '*' and self.isMatchCal(s, i, p, j+2))

#当前匹配字符的下一个是*号...说明可能匹配多个

if j+1 < plen and p[j+1] == '*' :

if p[j] == '.' or p[j] == s[i] :

return self.isMatchCal(s, i+1, p, j) or self.isMatchCal(s, i, p, j+2)

else :

return self.isMatchCal(s, i, p, j+2)

#或者当前匹配字符的下一个不是*号，但是当前字符匹配成功，则继续匹配

#如果不成功，说明出错了...

else :

if j < plen and (p[j] == '.' or p[j] == s[i]) :

return self.isMatchCal(s, i+1, p, j+1)

else :

return False

def isMatch(self, s, p):

"""

:type s: str

:type p: str

:rtype: bool

"""

return self.isMatchCal(s, 0, p, 0)

存在的问题是太慢了，勉强2400ms多过了…呵呵。

上网查了下，比较快的方法应该用动态规划：

给上原文链接：http://www.cnblogs.com/zuoyuan/p/3781773.html

然后继续：

class Solution(object):
    def isMatch(self, s, p):
        """
        :type s: str
        :type p: str
        :rtype: bool
        """
        lens = len(s)
        lenp = len(p)
        #初始化一个...额链表
        dp = [ [False for i in range(lenp+1)] for j in range(lens + 1) ]
        dp[0][0] = True
        
        #这里注意下, i对应的是p[i-1], dp[0][i]表示s长度为0,p[i-1]对应项
        for i in range(2, lenp + 1) :
            if p[i-1] == '*' :
                dp[0][i] = dp[0][i-2]
        
        #注意：这里实际上是，用p对s一一匹配..从p[0]开始
        #如果dp[i][j]实际上是s长度为i, p长度为j时的匹配结果。
        for i in range(1, lens + 1) :
            for j in range(1, lenp + 1):
                #如果当前项是.,则可以匹配任意字符,如果dp[i-1][j-1]正确了，则该位也能匹配正确。
                if p[j-1] == '.':
                    dp[i][j] = dp[i-1][j-1]
                #如果当前项是*，则要看d[i][j-1]或者d[i][j-2]是否匹配正确：
                #    如果d[i][j-1]正确，说明上一位的字符匹配成功，这一位只需要匹配一个即可匹配成功。
                #    如果上两位正确，则当前位不匹配可得正确。
                #如果都不正确，说明要判断s[i-1] 和 p[j-2]的字符是否能匹配上('.'是通配)，匹配的上，则可以匹配。
                elif p[j-1] == '*':
                    dp[i][j] = dp[i][j-1] or dp[i][j-2] or (dp[i-1][j] and (s[i-1]==p[j-2] or p[j-2]=='.'))
                #如果是普通字符，则要d[i-1][j-1]匹配正确，且s[i-1] 和 p[j-1]字符匹配正确。
                else:
                    dp[i][j] = dp[i-1][j-1] and s[i-1]==p[j-1]
        
        #最后返回的是：s长度为lens，p长度为lenp的匹配结果。
        return dp[lens][lenp]

class Solution(object):

def isMatch(self, s, p):

"""

:type s: str

:type p: str

:rtype: bool

"""

lens = len(s)

lenp = len(p)

#初始化一个...额链表

dp = [ [False for i in range(lenp+1)] for j in range(lens + 1) ]

dp[0][0] = True

#这里注意下, i对应的是p[i-1], dp[0][i]表示s长度为0,p[i-1]对应项

for i in range(2, lenp + 1) :

if p[i-1] == '*' :

dp[0][i] = dp[0][i-2]

#注意：这里实际上是，用p对s一一匹配..从p[0]开始

#如果dp[i][j]实际上是s长度为i, p长度为j时的匹配结果。

for i in range(1, lens + 1) :

for j in range(1, lenp + 1):

#如果当前项是.,则可以匹配任意字符,如果dp[i-1][j-1]正确了，则该位也能匹配正确。

if p[j-1] == '.':

dp[i][j] = dp[i-1][j-1]

#如果当前项是*，则要看d[i][j-1]或者d[i][j-2]是否匹配正确：

# 如果d[i][j-1]正确，说明上一位的字符匹配成功，这一位只需要匹配一个即可匹配成功。

# 如果上两位正确，则当前位不匹配可得正确。

#如果都不正确，说明要判断s[i-1] 和 p[j-2]的字符是否能匹配上('.'是通配)，匹配的上，则可以匹配。

elif p[j-1] == '*':

dp[i][j] = dp[i][j-1] or dp[i][j-2] or (dp[i-1][j] and (s[i-1]==p[j-2] or p[j-2]=='.'))

#如果是普通字符，则要d[i-1][j-1]匹配正确，且s[i-1] 和 p[j-1]字符匹配正确。

else:

dp[i][j] = dp[i-1][j-1] and s[i-1]==p[j-1]

#最后返回的是：s长度为lens，p长度为lenp的匹配结果。

return dp[lens][lenp]

88ms，快了30倍？

我算是一个写注释的…额，dp的思想终究还是：dp[i][j]的状态和之前的关系…

嗯，就是这样了。不深入研究。

【LeetCode】10. Regular Expression Matching

Tagged on: LeetCode Python