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

题目主要信息:

• 一个正常字符串str，可能为空，只包含小写字母

• 一个模式串pattern，可能为空，只包含小写字母和‘*’与‘.’

• 模式中的字符'.'表示任意一个字符，而'*'表示它前面的字符可以出现任意次（包含0次）

• 求str与pattern是否能完全匹配

具体思路:

如果是只有小写字母，那么直接比较字符是否相同即可匹配，如果再多一个'.'，可以用它匹配任意字符，只要对应str中的元素不为空就行了。但是多了'*'字符，它的情况有多种，涉及状态转移，因此我们用动态规划。设dp[i][j]表示str前i个字符和pattern前j个字符是否匹配。（需要注意这里的i，j是长度，比对应的字符串下标要多1）

• 初始条件： 首先，毋庸置疑，两个空串是直接匹配，因此$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]$。

• 状态转移： 然后分别遍历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]$.

具体过程可以参考如下图示：

代码实现:

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

复杂度分析：

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