LeetCode in Python 10. Regular Expression Matching (正则表达式匹配)

正则表达式匹配涉及到两个字符串的匹配问题，类似于寻找最大公共子串，可使用动态规划思想解决。重点和难点在于如何构建正确的状态转移方程。

示例：

图1 正则表达式匹配输入输出 

代码：

class Solution:
    def isMatch(self, s: str, p: str) -> bool:
        m, n = len(s), len(p)
        dp = [[False] * (n + 1) for _ in range(m + 1)]
        dp[0][0] = True
        for j in range(1, n + 1):
            if p[j - 1] == '*':
                dp[0][j] = dp[0][j - 2]
        
        for i in range(1, m + 1):
            for j in range(1, n + 1):
                if p[j - 1] == s[i - 1] or p[j - 1] == '.':
                    dp[i][j] = dp[i - 1][j - 1]
                elif p[j - 1] == '*':
                    if p[j - 2] != s[i - 1] and p[j - 2] != '.':
                        dp[i][j] = dp[i][j - 2]
                    else:
                        dp[i][j] = dp[i - 1][j] or dp[i][j - 2]
        return dp[m][n]  

解释：

1）dp是一个储存是否可以匹配的状态矩阵，大小为(m + 1)*(n + 1)，其中首行首列分别表示字符串s为空和字符串p为空的情况。其中dp[0][0]代表s，p两者均为空，显然能匹配。对于s为空而p不为空的情况(即对应dp的首行dp[0][j])是否能匹配取决于p中的字符，若为‘*’则可消除前一个字符使其为空，匹配成功。反之若不为‘*’，则无法匹配成功。故此需要初始化首行：

(ps：状态转移矩阵dp大小为(m + 1)*(n + 1)，首行首列代表字符串为空的情况，故dp[i][j]对应s[i-1]和p[j-1])。

        m, n = len(s), len(p)

        dp = [[False] * (n + 1) for _ in range(m + 1)]

        dp[0][0] = True

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

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

                        dp[0][j] = dp[0][j - 2]

2）状态转移主要是判断p中的字符：

        若其为a-z的小写字母或字符‘.’，则直接与s中对应位置比较即可，若相同则dp[i][j] == dp[i - 1][j - 1]，这里需要注意字符‘.’可匹配任意字符，可归为p[i][j]==s[i][i]这类情况。

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

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

        若为字符‘*’，则需要考虑两种情况：

        1.字符'*'消除前一个字符，即p[j - 1] * 整体为空。出现此类情况是因为我们不想选择p[j - 1]，即p[j - 1]与对应位置的s[i - 1]不相等(需要注意的是这里的p[j - 1]不等于s[i - 1]包含两种情况，一是两者均为小写字母且不等，二是p[j - 1]不为‘.’)

         2.字符‘*’复制一次前一个字符，即p[j - 1] *=p[j - 1]p[j - 1]。出现此种情况是因为p[j - 1]与对应位置的s[i - 1]相等。

         3.字符‘*’复制k次前一个字符，即p[j - 1] *=p[j - 1]...p[j - 1] (共k次)。出现此种情况是因为p[j - 1]与对应位置的s[i - k + 1]相等。

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

                if p[j - 2] != s[i - 1] and p[j - 2] != '.':

                        dp[i][j] = dp[i][j - 2]

               else:

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

3）需要注意字符‘*’复制k次的情况，这里的k可以为0：

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

另求助以下代码超时，大家能否帮笔者检查修改：

class Solution:
    def isMatch(self, s: str, p: str) -> bool:
        def dfs(i, j):
            if i >= len(s) and j >= len(p):
                return True
            if j >= len(p):
                return False
            
            match = i < len(s) and (s[i] == p[j] or p[j] == '.')
            if (j + 1) < len(p) and p[j + 1] == '*':
                return (dfs(i, j + 2) or (match and dfs(i + 1, j)))
            if match:
                return dfs(i + 1, j + 1)
            return False
        return dfs(0, 0) 

附上同样运用动态规划的最长公共子序列以及编辑距离的代码实现：

LeetCode in Python 300. Longest Increasing Subsequence (最长递增子序列)-CSDN博客

LeetCode in Python 72. Edit Distance (编辑距离)-CSDN博客