Leetcode算法——44、正则式匹配

给定一个输入字符串 s 和一个模式字符串 p，实现正则匹配，支持’?‘和’*’。

规则：

• ‘?’ 可以匹配任何单个字符
• ‘*’ 可以匹配任何字符的序列（包括空序列）
• 需要匹配整个输入字符串 s，不能部分匹配。

备注：

• 字符串 s 只会包含小写 a-z，可以为空。
• 字符串 p 只会包含小写 a-z、? 或 *，可以为空。

Example 1:
Input:
s = “aa”
p = “a”
Output: false
Explanation: “a” does not match the entire string “aa”.

Example 2:
Input:
s = “aa”
p = ""
Output: true
Explanation: '’ matches any sequence.

Example 3:
Input:
s = “cb”
p = “?a”
Output: false
Explanation: ‘?’ matches ‘c’, but the second letter is ‘a’, which does not match ‘b’.

Example 4:
Input:
s = “adceb”
p = “ab”
Output: true
Explanation: The first ‘’ matches the empty sequence, while the second '’ matches the substring “dce”.

Example 5:
Input:
s = “acdcb”
p = “a*c?b”
Output: false

思路

这道题与Leetcode算法——10、实现正则匹配很相似，不同之处在于匹配规则不同。

1、递归法

从左到右依次扫描 s 和 p 的每个字符，看是否可以匹配。

• 如果 s 为空，则只有 p 全部为 *，才能匹配上。
• 否则：
• • 如果首字符相同，或者 p 首字符为 ?，则可以匹配上，继续递归匹配 s[1:] 和 p[1:]
• • 如果 p 首字符为 * ，则可以尝试两种情况：
• • （1）试探让 * 表示 s 的首字符，s 右移一位，* 保留，继续递归匹配 s[1:] 和 p
• • （2）试探让 * 表示空字符，略过 *，s不变，继续递归匹配 s 和 p[1:]
• • 这两种情况是 or 的关系，只要有一个为真，则说明可以匹配上。

2、改进版

沿用上面的递归方法的思路，额外开辟一个空间：将上述过程中的每次子字符串的匹配结果，专门用一个词典存储起来，这样之后再次用到的话，直接取出即可，不必再计算一遍。

为什么有可能再次用到？关键在于上面说的特殊情况，即 p 的首字符是 * 的情况。这时候会分成两种情况，两者是 or 的关系，都需要计算出结果，这时候就可能会重复计算了。

python实现

def isMatch(s, p):
    """
    :type s: str
    :type p: str
    :rtype: bool
    递归法。
    """
    if not p:
        return not s
    
    if s: # s不为空
        if p[0] in [s[0], '?']: # 首字符相同，或者p首字符为?，都可以匹配上
            return isMatch(s[1:], p[1:]) # 各右移一位，继续匹配
        elif p[0] == '*': # p首字符为*
            # isMatch(s[1:], p)试探让*表示s的首字符，s右移一位，*保留
            # isMatch(s, p[1:])试探让*表示空字符，略过*，s不变
            return isMatch(s[1:], p) or isMatch(s, p[1:]) 
    elif p[0] == '*': # s为空，则只有p全部为*，才可以匹配上
        return isMatch(s, p[1:])
    
    return False

def isMatch2(s, p):
    """
    :type s: str
    :type p: str
    :rtype: bool
    改进版。
    """
    p.replace('**','*')
    memo = {}
    def dp(i, j):
        if (i, j) not in memo:
            ans = False
            if j == len(p):
                ans = i == len(s)
            elif i < len(s):
                if p[j] in [s[i], '?']:
                    ans = dp(i+1, j+1)
                elif p[j] == '*':
                    if (i, j+1) in memo:
                        ans = dp(i, j+1) or dp(i+1, j)
                    else:
                        ans = dp(i+1, j) or dp(i, j+1) 
            elif p[j] == '*':
                ans = dp(i, j+1)
            memo[i, j] = ans
        return memo[i, j]
    return dp(0, 0)      
    
if '__main__' == __name__:
    s = "adceb"
    p = "*a*b"
    print(isMatch(s, p))