题目

给你一个字符串 s 和一个字符规律 p，请你来实现一个支持 ‘.’ 和 ‘*’ 的正则表达式匹配。

'.' 匹配任意单个字符 '*' 匹配零个或多个前面的那一个元素

所谓匹配，是要涵盖 整个 字符串 s的，而不是部分字符串。

说明:

s 可能为空，且只包含从 a-z 的小写字母。 p 可能为空，且只包含从 a-z 的小写字母，以及字符 . 和 *。 示例 1:

输入: s = "aa" p = "a" 输出: false 解释: "a" 无法匹配 "aa" 整个字符串。

示例 2:

输入: s = "aa" p = "a*" 输出: true 解释: 因为 '*' 代表可以匹配零个或多个前面的那一个元素, 在这里前面的元素就是 'a'。因此，字符串 "aa" 可被视为 'a' 重复了一次。

示例 3:

输入: s = "ab" p = ".*" 输出: true 解释: ".*" 表示可匹配零个或多个（'*'）任意字符（'.'）。

示例 4:

输入: s = "aab" p = "c*a*b" 输出: true 解释: 因为 '*' 表示零个或多个，这里 'c' 为 0 个, 'a' 被重复一次。因此可以匹配字符串 "aab"。

示例 5:

输入: s = "mississippi" p = "mis*is*p*." 输出: false

思路

dp[i][j]表示前i个字符串字符与前j个正则表达式字符匹配情况。对于正则表达式中的普通字符只需要判断对应位字符是否相同即可。对于正则表达式中的字符’.’，则字符串中的任意字符都可以匹配。题中最重要的部分是对字符’*‘的匹配，在匹配’*'时需要考虑符号之前的字符，一共会存在两种情况：

'*'之前的字符出现了一次以上'*'之前的字符没有出现

这两种情况字符串和正则表达式都是匹配的。所以当正则表达式第j位是’*‘时，当字符串第i位与正则表达式第j-1位匹配时，dp[i][j]可以在dp[i][j-2]（’*‘之前的字符没有出现）或dp[i-1][j](’*‘之前的字符出现了一次以上）为真时为真。当不匹配时，dp[i][j]可以在dp[i][j-2]（’*'之前的字符没有出现）为真时为真。

代码

class Solution { public: bool isMatch(string s, string p) { int m = s.size(); int n = p.size(); vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0)); dp[0][0] = true; for(int i = 0; i <= m; i++) for(int j = 1; j <= n; j++){ if(p[j-1] == '*'){ dp[i][j] |= dp[i][j-2]; if(matches(s, p, i, j-1)) dp[i][j] |= dp[i-1][j]; } else if(matches(s, p, i, j)) dp[i][j] |= dp[i-1][j-1]; } return dp[m][n]; } bool matches(string s, string p, int i, int j){ if(i == 0) return false; if(p[j-1] == '.') return true; return s[i-1] == p[j-1]; } };