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

题目：

分析：

涉及两个字符串的相关操作问题，考虑使用动态规划。题目中的正则表达式匹配包含两个特殊字符，'*'和'.'；其中，'*'表示前面的字符可以出现任意次（包括0次），这说明'*'不可能出现在pattern中第一个位置；'.'可以表示任意字符，说明 '.' 可以出现在 pattern 的第一个位置且'.' 必须占一个字符空间（不能为0字符）。

为便于后面分析，下面画出一个示例的dp表（pattern = "c*a*.", str = "aad"）。

思路：

在上面的 dp 表中，dp[i][j] 表示 pattern[0:i] 是否能匹配到 str[0:j]，注：str[0:j] 表示 "str[0]str[1]...str[j-1]"，比如str[0:2] = "aa"。

仔细观察上面的 dp 表：

1 当 pattern[i - 1]=='*' 时：看'*'前面的字符pattern[i - 2]

1.1 pattern[i - 2] == str[j - 1] 或 pattern[i - 2] =='.'时 (dp表中dp[3][1], dp[3][2])

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

上式说明： 在这种情况下，pattern[0:i]能否匹配到str[0:j] 与pattern[0:i-1]能否匹配到str[j], pattern[0:i] 能否匹配到 str[j - 1]，和pattern[i - 2] 能否匹配到 str[0:j] 有关。三种关系分别对应'*'表示前面字符的出现1次、任意次和0次。

1.2 pattern[i - 2] != str[j - 1] 时 （dp表中dp[1][1]）

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

这种情况下，dp[i][j] 只与'*'表示前面的字符出现0次有关, 即 pattern[0:i-2] 是否能匹配到 str[0:j]

2 当pattern[i - 1]==普通字符或'.'时：

2.1 pattern[i - 1] == str[i - 1] 或 pattern[i - 1] =='.'

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

当前字符相等，判断前一个字符是否可以匹配

2.2 pattern[ i - 1] != str[j - 1]

dp[i][j] = false

当前字符不相等，直接无法匹配

dp数组初始化：

首先 dp[0][0] = true; 需要初始化dp数组的第一列, 由上表可以看出：dp[i][0] 的值与 pattern[i - 1] == '*'有关。

由于'*' 不可能出现在第一个字符，因此从 i = 2开始遍历初始化, 当 pattern[i - 1] == '*' 时，

dp[i][0] = dp[i - 2][0]

代码：

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param str string字符串 
     * @param pattern string字符串 
     * @return bool布尔型
     */
    bool match(string str, string pattern) {
        // write code here
        int m = str.length(), n = pattern.length();
        vector<vector<bool>> dp(n + 1, vector<bool>(m + 1, false));
	  // 初始化
        dp[0][0] = true;
        for (int i = 2; i <= n; ++i) if (pattern[i - 1] == '*' ) dp[i][0] = dp[i -2][0]; 
	  // 动态规划
        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= m; ++j) {
			  // 1
                if(pattern[i - 1] == '*') {
				  // 1.1
                    if (pattern[i - 2] == str[j - 1] || pattern[i - 2] == '.')
                        dp[i][j] = dp[i][j - 1] || dp[i - 1][j] || dp[i - 2][j];
				  // 1.2
                    else dp[i][j] = dp[i - 2][j];
                }
			  // 2 
                else {
				  // 2.1
				  if (pattern[i - 1] == str[j - 1] || pattern[i - 1] == '.')
                    dp[i][j] = dp[i - 1][j - 1];
				  // 2.2
				  else 
					dp[i][j] = false;
                }
            }
        }
        return dp[n][m];
    }
};