题目描述
请实现一个函数用来匹配包括'.'和'*'的正则表达式。
模式中的字符'.'表示任意一个字符，而'*'表示它前面的字符可以出现任意次（含0次）。
在本题中，匹配是指字符串的所有字符匹配整个模式。
例如，字符串"aaa"与模式"a.a"和"ab*ac*a"匹配，但是与"aa.a"和"ab*a"均不匹配。
数据范围
输入字符串长度 [0,300]。
样例
输入： s="aa" p="a*" 输出:true
题意
字符 . 存在一种情况：
- 可以指代任何一个字符。
字符 * 存在三种情况：
*前面的字符出现了0次。
*前面的字符出现了1次
*前面的字符出现了n次。
方法一：动态规划 O(nm)
状态表示： f[i][j] = true 表示 s[i...] 和 p[j...] 相匹配，即 s 从 i 开始以后的字符串与 p 从 j 开始以后的字符串相匹配。
状态转移：
p[j] 是正常字符，f[i][j] = s[i] == p[j] && f[i+1][j+1] 。
如果遇到的是正常的字符，需要判断 s[i] 和 p[j] 是否相等，并且 i 和 j 之后的字符是否都相匹配。
p[j] 是 . ，f[i][j] = f[i+1][j+1] 。
如果遇到了. ，s[i] 和 p[j] 不需要判断是否相等，. 可以指代任何一个字符，所以只用判断 i 和 j 后面的字符是否想匹配即可。
p[j+1] 是 * ，f[i][j] = f[i][j+2] || f[i+1][j] 。
如果遇到了 * ，由于 p[j] 在 s[i] 中出现 0 次或 n 次，所以要分成两种情况判断。第一种是出现 0 次的情况，这时候就需要判断 p[j+2] 是否与 s[i] 相匹配，因为 p[j] 可能在 s[i] 中没有出现；第二种是出现了 n 次的情况， 这时候就要继续取判断 p[j] 是否与 s[i+1] 相匹配。
class Solution { public: vector<vector<int>> f; int n, m; bool isMatch(string s, string p) { n = s.size(); m = p.size(); f = vector<vector<int>>(n + 1, vector<int>(m + 1, -1)); return dp(0, 0, s, p); } bool dp(int x, int y, string s, string p) { if (f[x][y] != -1) return f[x][y]; //判断是否当前状态已经访问过 if (y == m) return f[x][y] = x == n; //判断模式串遍历完后字符串是否也遍历完 //情况1&&情况2，s[x]与p[y]匹配或p[y]为'.' bool first_match = x < n && (s[x] == p[y] || p[y] == '.'); bool ans; //情况3，p[y+1]为'*' if (y + 1 < m && p[y + 1] == '*') //'*'前面字母出现0次||'*'前面字母出现n次 ans = dp(x, y + 2, s, p) || first_match && dp(x + 1, y, s, p); else //继续向后匹配 ans = first_match && dp(x + 1, y + 1, s, p); return f[x][y] = ans; } };
欢迎大家在评论区交流~
