题解 | #正则表达式匹配#

题目主要信息:

• 一个正常字符串str，可能为空，只包含小写字母
• 一个模式串pattern，可能为空，只包含小写字母和‘*’与‘.’
• 模式中的字符'.'表示任意一个字符，而'*'表示它前面的字符可以出现任意次（包含0次）
• 求str与pattern是否能完全匹配

举一反三：

学习完本题的思路你可以解决如下题目：

BM65 最长公共子序列(二)

BM66.最长公共子串

BM71.最长上升子序列(一)

BM73 最长回文子串

BM75 编辑距离(一)

BM77 最长的括号子串

方法：动态规划（推荐使用）

知识点：动态规划

动态规划算法的基本思想是：将待求解的问题分解成若干个相互联系的子问题，先求解子问题，然后从这些子问题的解得到原问题的解；对于重复出现的子问题，只在第一次遇到的时候对它进行求解，并把答案保存起来，让以后再次遇到时直接引用答案，不必重新求解。动态规划算法将问题的解决方案视为一系列决策的结果

思路：

如果是只有小写字母，那么直接比较字符是否相同即可匹配，如果再多一个'.'，可以用它匹配任意字符，只要对应str中的元素不为空就行了。但是多了'*'字符，它的情况有多种，涉及状态转移，因此我们用动态规划。

具体做法：

• step 1：设dp[i][j]表示str前i个字符和pattern前j个字符是否匹配。（需要注意这里的i，j是长度，比对应的字符串下标要多1）

• step 2： （初始条件） 首先，毋庸置疑，两个空串是直接匹配，因此$dp[0][0]=truedp[0][0]=true$。然后我们假设str字符串为空，那么pattern要怎么才能匹配空串呢？答案是利用'*'字符出现0次的特性。遍历pattern字符串，如果遇到'*'意味着它前面的字符可以出现0次，要想匹配空串也只能出现0，那就相当于考虑再前一个字符是否能匹配，因此$dp[0][i]=dp[0][i-2]dp[0][i]\; =\; dp[0][i\; -\; 2]$。

• step 3： （状态转移） 然后分别遍历str与pattern的每个长度，开始寻找状态转移。首先考虑字符不为'*'的简单情况，只要遍历到的两个字符相等，或是pattern串中为'.'即可匹配，因此最后一位匹配，即查看二者各自前一位是否能完成匹配，即$dp[i][j]=dp[i-1][j-1]dp[i][j]\; =\; dp[i\; -\; 1][j\; -\; 1]$。然后考虑'*'出现的情况：

  1. pattern[j - 2] == '.' || pattern[j - 2] == str[i - 1]：即pattern前一位能够多匹配一位，可以用'*'让它多出现一次或是不出现，因此有转移方程$dp[i][j]=dp[i-1][j]\mathrm{\mid }\mathrm{\mid }dp[i][j-2]dp[i][j]\; =\; dp[i\; -\; 1][j]\; ||\; dp[i][j\; -\; 2]$
  2. 不满足上述条件，只能不匹配，让前一个字符出现0次，$dp[i][j]=dp[i][j-2]dp[i][j]\; =\; dp[i][j\; -\; 2]$.

图示：

Java实现代码：

import java.util.*;
public class Solution {
    public boolean match (String str, String pattern) {
        int n1 = str.length();
        int n2 = pattern.length();
        //dp[i][j]表示str前i个字符和pattern前j个字符是否匹配
        boolean[][] dp = new boolean[n1 + 1][n2 + 1]; 
        //遍历str每个长度
        for(int i = 0; i <= n1; i++){  
            //遍历pattern每个长度
            for(int j = 0; j <= n2; j++){ 
                //空正则的情况
                if(j == 0){ 
                    dp[i][j] = (i == 0 ? true : false);
                //非空的情况下 星号、点号、字符
                }else{ 
                    if(pattern.charAt(j - 1) != '*'){
                        //当前字符不为*，用.去匹配或者字符直接相同
                        if(i > 0 && (str.charAt(i - 1) == pattern.charAt(j - 1) || pattern.charAt(j - 1) == '.')){
                            dp[i][j] = dp[i - 1][j - 1];
                        }
                    }else{
                        //碰到*
                        if(j >= 2){
                            dp[i][j] |= dp[i][j - 2];
                        }
                        //若是前一位为.或者前一位可以与这个数字匹配
                        if(i >= 1 && j >= 2 && (str.charAt(i - 1) == pattern.charAt(j - 2) || pattern.charAt(j - 2) == '.')){
                            dp[i][j] |= dp[i - 1][j];
                        }
                    }
                }
            }
        }
        return dp[n1][n2];
  }
}

C++实现代码：

class Solution {
public:
    bool match(string str, string pattern) {
        int n1 = str.length();
        int n2 = pattern.length();
        //dp[i][j]表示str前i个字符和pattern前j个字符是否匹配
        vector<vector<bool> > dp(n1 + 1, vector<bool>(n2 + 1, false)); 
        //两个都为空串自然匹配
        dp[0][0] = true; 
        //初始化str为空的情况，字符串下标从1开始
        for(int i = 2; i <= n2; i++){ 
            //可以让自己前面个字符重复0次
            if(pattern[i - 1] == '*') 
                //与再前一个能够匹配空串有关
                dp[0][i] = dp[0][i - 2]; 
        }
        //遍历str每个长度
        for(int i = 1; i <= n1; i++){ 
            //遍历pattern每个长度
            for(int j = 1; j <= n2; j++){ 
                //当前字符不为*，用.去匹配或者字符直接相同
                if(pattern[j - 1] != '*' && (pattern[j - 1] == '.' || pattern[j - 1] == str[i - 1])){ 
                      dp[i][j] = dp[i - 1][j - 1];
                //当前的字符为*
                }else if(j >= 2 && pattern[j - 1] == '*'){ 
                    //若是前一位为.或者前一位可以与这个数字匹配
                    if(pattern[j - 2] == '.' || pattern[j - 2] == str[i - 1]) 
                        //转移情况
                        dp[i][j] = dp[i - 1][j] || dp[i][j - 2];  
                    else
                        //不匹配
                        dp[i][j] = dp[i][j - 2]; 
                }
            }
        }
        return dp[n1][n2];
    }
};

Python代码实现：

class Solution:
    def match(self , str: str, pattern: str) -> bool:
        n1 = len(str)
        n2 = len(pattern)
        #dp[i][j]表示str前i个字符和pattern前j个字符是否匹配
        dp = [[False] * (n2 + 1) for i in range(n1 + 1)]
        #两个都为空串自然匹配
        dp[0][0] = True 
        #初始化str为空的情况，字符串下标从1开始
        for i in range(2, n2 + 1): 
            #可以让自己前面个字符重复0次
            if pattern[i - 1] == '*': 
                #与再前一个能够匹配空串有关
                dp[0][i] = dp[0][i - 2] 
        #遍历str每个长度
        for i in range(1, n1 + 1): 
            #遍历pattern每个长度
            for j in range(n2 + 1): 
                #当前字符不为*，用.去匹配或者字符直接相同
                if pattern[j - 1] != '*' and (pattern[j - 1] == '.' or pattern[j - 1] == str[i - 1]): 
                      dp[i][j] = dp[i - 1][j - 1]
                #当前的字符为*
                elif j >= 2 and pattern[j - 1] == '*': 
                    #若是前一位为.或者前一位可以与这个数字匹配
                    if pattern[j - 2] == '.' or pattern[j - 2] == str[i - 1]: 
                        #转移情况
                        dp[i][j] = dp[i - 1][j] or dp[i][j - 2] 
                    else:
                        #不匹配
                        dp[i][j] = dp[i][j - 2] 
        return dp[n1][n2]

复杂度分析：

• 时间复杂度：$O(mn)O(mn)$，其中$mm$和$nn$分别为字符串和模版串的长度，初始化遍历矩阵一边，状态转移遍历整个dp矩阵
• 空间复杂度：$O(mn)O(mn)$，动态规划辅助数组dp的空间