正则表达式匹配 —— 动态规划（C++）

正则表达式匹配 描述

  请实现一个函数用来匹配包括’.‘和’*'的正则表达式。

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

  在本题中，匹配是指字符串的所有字符匹配整个模式。例如，字符串"aaa"与模式"a.a"和"ab*ac*a"匹配，但是与"aa.a"和"ab*a"均不匹配。

数据范围：

1. str 只包含从 a-z 的小写字母。

2. pattern 只包含从 a-z 的小写字母以及字符 . 和 *，无连续的 ‘*’。

3. 0≤str.length≤26

4. 0≤pattern.length≤26

示例1

输入：
"aaa","a*a"
返回值：
true
说明：
中间的*可以出现任意次的a，所以可以出现1次a，能匹配上 

示例2

输入：
"aad","c*a*d"
返回值：
true
说明：
因为这里 c 为 0 个，a被重复一次， * 表示零个或多个a。因此可以匹配字符串 "aad"。

示例3

输入：
"a",".*"
返回值：
true
说明：
".*" 表示可匹配零个或多个（'*'）任意字符（'.'）

示例4

输入：
"aaab","a*a*a*c"
返回值：
false

思路/解法（动态规划算法）

参考牛客网——正则表达式匹配官方题解：https://www.nowcoder.com/practice/28970c15befb4ff3a264189087b99ad4?tpId=13&tqId=1375406&ru=/exam/oj/ta&qru=/ta/coding-interviews/question-ranking&sourceUrl=%2Fexam%2Foj%2Fta%3Fpage%3D1%26tpId%3D13%26type%3D13

动态规划

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

思路

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

具体做法

• step 1：设dp[i][j]表示str前i个字符和pattern前j个字符是否匹配。（需要注意这里的i，j是长度，比对应的字符串下标要多1）
• step 2： （初始条件） 首先，毋庸置疑，两个空串是直接匹配，因此dp[0][0] = true。然后我们假设str字符串为空，那么pattern要怎么才能匹配空串呢？答案是利用’*‘字符出现0次的特性。遍历pattern字符串，如果遇到’*'意味着它前面的字符可以出现0次，要想匹配空串也只能出现0，那就相当于考虑再前一个字符是否能匹配，因此dp[0][i] = dp[0][i-2]。
• step 3： （状态转移） 然后分别遍历str与pattern的每个长度，开始寻找状态转移。首先考虑字符不为’*‘的简单情况，只要遍历到的两个字符相等，或是pattern串中为’.‘即可匹配，因此最后一位匹配，即查看二者各自前一位是否能完成匹配，即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] || dp[i][j-2]。
  2. 不满足上述条件，只能不匹配，让前一个字符出现0次，dp[i][j] = dp[i][j-2]。

图示：

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param str string字符串 
     * @param pattern string字符串 
     * @return bool布尔型
     */
    bool match(string str, string pattern) 
    {
        int col = pattern.size();//行
        int row = str.size();//列
        //dp[i][j]表示str前i个字符和pattern前j个字符是否匹配
        vector<vector<bool>> dp(row+1,vector<bool>(col+1,false));
        //两个都为空的情况下肯定是匹配的
        dp[0][0] = true;
        //初始化当str为空的情况，字符串下标从1开始
        for(int i = 2;i <= col;i++)
        {
            //该情况下可以让前面那个字符重复0次
            if(pattern[i-1] == '*')
                //简单的状态转移，当前字符跟前面的前面那个字符是否匹配是相关联的。
                dp[0][i] = dp[0][i-2];
        }
        
        //遍历str的每个字符，从下标为0的字符开始
        for(int i = 1;i <= row;i++)
        {
            //遍历pattern的每个字符，从下标为0的字符开始
            for(int j = 1;j <= col;j++)
            {
                //当前字符不为*,用。匹配或者字符直接相同
                if(pattern[j-1] != '*' && (pattern[j-1] == '.' || pattern[j-1] == str[i-1]))
                    //如果匹配，那么对应dp[i][j]的状态转移是dp[i-1][j-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-1][j]和dp[i][j-2]都可，即逻辑或
                        dp[i][j] = dp[i-1][j] || dp[i][j-2];
                    else
                        //否则不匹配，状态转移上一个字符的状态
                        dp[i][j] = dp[i][j-2];
                }
            }
        }
        return dp[row][col];
    }
};