【经典题目】正则表达式匹配，通配符匹配——字符串的dp匹配问题

引言

核心的dp状态设计还是老方法，但是给出了通配符这个新东西。因此要对这类操作有新的思考。

其中涉及到了一个状态压缩的方法比较巧妙。

题目

思考，状态还是自然定义为

dp[i][j]

，表示

s[:i]

和

p[:j]

匹配的情况。对于状态的转移我们考虑两种大的情况：

1. p[j+1] == '*'

   这是一个特殊的情况，我们需要整体处理

   a*

   这种形式

2. s[i] == p[j] or '.'

   此时是匹配的，可以化为

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

3. 当

   p = '*'

   ，需要看前一个字符的匹配情况，

   （1）能匹配正确，此时枚举能需要重复几次，1次：

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

   ， 两次：

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

   …

   （2）无法匹配上，此时让前一个字符消失

   dp[i][j-2]

4. 当

   p = '*'

   有情况

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

   一次是重复0次，重复一次，重复两次。。。

状态压缩：

对比前后两个状态

6.

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

7.

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

可以很明显的看出

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

还需要特别处理，边界的代码，保证保证"a"可以匹配""空*

因此得到代码：

class Solution:
    def isMatch(self, s: str, p: str) -> bool:
        n = len(s)
        m = len(p)
        dp = [[False]*(m+1) for _ in range(n+1)]
        # 为了在索引上进行匹配
        s = ' '+s
        p = ' '+p
        dp[0][0] = True     
        # 预处理，保证"a*"可以匹配""空  
        for j in range(2, m + 1):
            dp[0][j] = dp[0][j - 2] and p[j] == '*'
            
        for i in range(1, n + 1):
            for j in range(1, m + 1):
                if p[j] == '*':
                    if s[i] == p[j - 1] or p[j - 1] == '.':
                        dp[i][j] = dp[i][j - 2] or dp[i - 1][j]
                    else: dp[i][j] = dp[i][j - 2]
                elif s[i] == p[j] or p[j] == '.':
                    dp[i][j] = dp[i - 1][j - 1]
        return dp[n][m]
           

例题2：通配符匹配

与正则表达式匹配类似的题目，需要考虑如何处理两个特殊的匹配符号。

• 对于

  ?

  很容易处理，可以当成替换操作，只需要

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

• 对于

  *

  就需要特殊处理，我们可以视为一个删除（匹配空）操作

  dp[i][j-1]

  或者添加（表示当前星号匹配了当前的位置的字符）操作

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

  ，

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

另外需要注意边界的处理，

***

也是可以匹配空字符串的。

class Solution:
    def isMatch(self, s: str, p: str) -> bool:
        n = len(s)
        m = len(p)
        dp = [[False]*(m+1) for _ in range(n+1)]
        dp[0][0] = True
        # 考虑边界的特殊情况，"*"是可以匹配空的
        for i in range(1, m+1):
            if p[i-1] == '*':
                dp[0][i] = True
            else:
                break
        for i in range(1,n+1):
            for j in range(1,m+1):
                if p[j-1] == '*':
                    # 匹配当前，或空匹配
                    dp[i][j] = dp[i-1][j] | dp[i][j-1]
                elif p[j-1] == '?' or p[j-1] == s[i-1]:
                    dp[i][j] = dp[i-1][j-1]
        return dp[n][m]