10. 正则表达式匹配

题目描述

2个字符串s和p，p中包含小写字母，.，*

其中

. 匹配任意单个字符

* 匹配零个或多个前面的那一个元素

保证每次出现字符 * 时，前面都匹配到有效的字符

按照这个规则来判断s和p是否匹配。

解题思路

本题根据经验，用动态规划的知识进行解决。

状态转移方程和状态表示

2个字符串则用二维来进行表示状态方程：

dp[i][j]表示s(0,i)和p(0,j)是否匹配。

计算：（以p字符串进行分类讨论）

p[j]!=*

s[i]与p[j]是否相等：s[i]==p[j]||p[j]==.都表示相等，dp[i-1][j-1]

p[j]==*

匹配0个：dp[i][j-2]

匹配1个：dp[i-1][j-2]并且s[i]==p[j-1]

匹配2个：dp[i-2][j-1]并且s[i]==p[j-1]

…匹配n个。同上

那么dp[i][j]=dp[i][j-2]||dp[i-1][j-2]||dp[i-2][j-2]||.......

上面的式子改写一下：（条件s[i]==p[j-1]||p[j]=='.'）

dp[i-1][j]=dp[i-1][j-2]||dp[i-2][j-2]||dp[i-3][j-2]||.......

合并得：

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

初始化和返回值

为了更好的计算，我们在每个字符前面的加上一个空格，然后全部从第1个字符开始遍历计算。

根据状态表示的含义及其可能的越界来进行初始化。

因为要用到i-1。所有要注意dp[0][n]

• dp[0][0]==true（0个字符和0个字符肯定是匹配的）
• dp[0][1]==false（0个字符和1个字符肯定是不匹配的）
• dp[0][2]== 0个字符和2个字符的情况不能确定，我们要进行判断：

根据题目的要求，可以得到第一个字串肯定不能是*——保证每次出现字符 * 时，前面都匹配到有效的字符——所有如果p[2]是*则为true。其他情况为false。

• 所有j为偶数的情况，只要为*，且dp[0][j-2]为true则dp[0][j]为true。否则false。

遍历顺序从左到右，从上到下

返回值：dp[s.size()][p.size()]

代码

class Solution {
public:
    bool isMatch(string s, string p) {
        int m=s.size(),n=p.size();
        vector<vector<bool>> dp(m+1,vector<bool>(n+1));
        s=" "+s;p=" "+p;
        
        dp[0][0]=true;
        for(int j=2;j<=n;j+=2) dp[0][j]=p[j]=='*'&&dp[0][j-2];

        for(int i=1;i<=m;i++)
        {
            for(int j=1;j<=n;j++)
            {
                if(p[j]=='*') dp[i][j]=dp[i][j-2]||((s[i]==p[j-1]||p[j-1]=='.')&&dp[i-1][j]);
                else dp[i][j]=(s[i]==p[j]||p[j]=='.')&&dp[i-1][j-1];
            }
        }

        return dp[m][n];
    }
};