LeetCode第十题：正则表达式匹配
- 学习
- 2023-09-18
- 56热度
- 0评论
1.题目描述
给你一个字符串 s 和一个字符规律 p，请你来实现一个支持 '.' 和 '*' 的正则表达式匹配。
'.'匹配任意单个字符'*'匹配零个或多个前面的那一个元素
所谓匹配，是要涵盖 整个 字符串 s的，而不是部分字符串。
示例 1：
输入：s = "aa", p = "a"
输出：false
解释："a" 无法匹配 "aa" 整个字符串。
提示：
1 <= s.length <= 201 <= p.length <= 20s只包含从a-z的小写字母。p只包含从a-z的小写字母，以及字符.和*。- 保证每次出现字符
*时，前面都匹配到有效的字符
2.解题思路
解法一：递归
- 描述：递归的结束条件是当模式串为空时，返回字符串是否为空，缩小规模通过查看首字符是否匹配和模式串的第二个字符是否为*来减少字符串或者模式串的长度进而减小规模。
- 时间复杂度：较为复杂
- 空间复杂度：较为复杂
- 参考代码：
java版：
class Solution {
public boolean isMatch(String s, String p) {
// 递归出口
// 规模逐渐减小，如果模式串为空，只有当字符串也为空时才会匹配成功
if (p.isEmpty()) {
return s.isEmpty();
}
// 判断字符串和模式串的第一个字符是否一致
// 条件是字符串不为空并且字符串和模式串的第一个字符相同或者模式串的第一个字符是. 因为.可以匹配任意单个字符
boolean firstMatch = (!s.isEmpty() && (s.charAt(0) == p.charAt(0) || p.charAt(0) == '.'));
// 只有模式串的长度大于等于2的时候，才会考虑*
if (p.length() >= 2 && p.charAt(1) == '*') {
// 满足条件的话分两种情况，第一是*匹配的是起那么字符出现0次，那么直接让s和模式串*后面的进行匹配
// 第二是代表出现1次或者多次，那么让s的下一位和p进行匹配，代表*匹配了一位
// 例如s==aaabc，p==a*bc，满足第一位字符相等，跳过第一个a，让aabc和a*bc匹配，还是满足，直到bc和a*bc去满足第一种情况
return isMatch(s, p.substring(2)) || (firstMatch && isMatch(s.substring(1), p));
} else {
// 没有*号的话就继续匹配两个字符串的下一位
return firstMatch && isMatch(s.substring(1), p.substring(1));
}
}
}C++版：
class Solution {
public:
bool isMatch(string s, string p)
{
// 递归出口
// 规模逐渐减小，如果模式串为空，只有当字符串也为空时才会匹配成功
if (p.empty())
{
return s.empty();
}
// 判断字符串和模式串的第一个字符是否一致
// 条件是字符串不为空并且字符串和模式串的第一个字符相同或者模式串的第一个字符是. 因为.可以匹配任意单个字符
bool firstMatch = (!s.empty() && (s[0] == p[0] || p[0] == '.'));
// 只有模式串的长度大于等于2的时候，才会考虑*
if (p.size() >= 2 && p[1] == '*')
{
// 满足条件的话分两种情况，第一是*匹配的是起那么字符出现0次，那么直接让s和模式串*后面的进行匹配
// 第二是代表出现1次或者多次，那么让s的下一位和p进行匹配，代表*匹配了一位
// 例如s==aaabc，p==a*bc，满足第一位字符相等，跳过第一个a，让aabc和a*bc匹配，还是满足，直到bc和a*bc去满足第一种情况
return isMatch(s, p.substr(2)) || (firstMatch && isMatch(s.substr(1), p));
}
else
{
// 没有*号的话就继续匹配两个字符串的下一位
return firstMatch && isMatch(s.substr(1), p.substr(1));
}
}
};C版：
bool isMatch(char* s, char* p) {
// 如果模式串为空，只有当字符串也为空时才会匹配成功
if (*p == '\0') {
return *s == '\0';
}
// 判断字符串和模式串的第一个字符是否匹配
bool firstMatch = (*s != '\0' && (*s == *p || *p == '.'));
// 如果模式串长度大于1且下一个字符是'*'
if (strlen(p) >= 2 && *(p + 1) == '*') {
// 两种情况：
// 1. '*'表示0个字符
// 2. '*'表示1个或多个前面的字符
return (isMatch(s, p + 2) ||
(firstMatch && isMatch(s + 1, p)));
}
else {
return firstMatch && isMatch(s + 1, p + 1);
}
}解法二：动态规划
- 描述：定义二维数组dp，dp[i][j]表示s的前i个字符和p的前j个字符是否匹配。然后进行初始化，将s为空字符串时，p必须是星号的组合形式才能与s匹配，状态转移方程是，s[i]=p[j]或者p[j]=.那么dp[i][j]=dp[i-1][j-1] 如果p[j]=* 则有两种情况，星号表示0个前一个字符或表示1个或多个前一个字符。这导致我们有两种可能的状态转移，dp[i][j-2](忽略*和前面的字符)或者dp[i-1][j](如果
s[i]与p[j-1]匹配或p[j-1]为'.') - 时间复杂度：O(m*n)。我们需要填充一个大小为(m+1)*(n+1)的表格，其中每个单元格的计算都是O(1)的复杂度。
- 空间复杂度：O(m*n)。我们需要一个的(m+1)*(n+1)二维数组来存储我们的dp值。
- 参考代码：
java版：
class Solution {
public boolean isMatch(String s, String p) {
int m = s.length();
int n = p.length();
// 定义一个bool类型的二维数组， dp[i][j]表示s的前i个字符与p的前j个字符是否匹配
// 这里m+1和n+1是为了处理空字符串或空数组的情况dp[0][0]表示两个空字符串是否匹配
boolean[][] dp = new boolean[m + 1][n + 1];
// 两个空字符串肯定匹配
dp[0][0] = true;
// 当s为空时，我们仍然需要知道与模式串是否匹配
// 比如a*是可以与空字符串匹配的，*可以代表前面字符出现0次或者多次
// 所以判断模式字符串中的*就行
// 后面的循环也需要用到这个初始化的值，否则都默认为false的话会导致错误
for (int j = 1; j <= n; j++) {
if (p.charAt(j - 1) == '*') {
// 当模式串的值为*时，说明前面的符号是可以为0的，所以值等于-2的值
dp[0][j] = dp[0][j - 2];
}
}
// 通过嵌套循环来将dp数组填满
// 外层循环遍历字符串中的每一个字符
for (int i = 1; i <= m; i++) {
// 内层循环遍历模式串的每一个字符，对于字符串的每一个字符
// 检查它与模式p的前j个字符是否匹配。
for (int j = 1; j <= n; j++) {
// 如果满足这个条件，说明当前的字符是匹配的，所以dp[i][j]取决于dp[i-1][j-1]
// 例如s=ab，p=ab，i=1,j=1,a=a,dp[1][1]=dp[0][0]=true
// 然后i=2,j=2，b=b,dp[2][2]=dp[1][1]=true
// 例如s=abc，p=a.c，i=1,j=1,a=a,dp[1][1]=dp[0][0]=true
// 然后i=2,j=2，s.charAt(1)=b，p.charAt(1)=. 这也是匹配的，所以dp[2][2]=dp[1][1]=true
// 然后i=3,j=3，c=c，dp[3][3] = dp[2][2] = true
if (s.charAt(i - 1) == p.charAt(j - 1) || p.charAt(j - 1) == '.') {
dp[i][j] = dp[i - 1][j - 1];
}
// 如果模式串中当前字符为*，表示前面的字符可以匹配0次或多次。
else if (p.charAt(j - 1) == '*') {
// 表示*匹配0次的时候，我们直接忽略*及其前面的字符
// 例如s="a"，p="ab*",s="",p="" dp[0][0]=true
// i=1,j=1,a=a,dp[1][1]=dp[0][0]=true,i=1,j=2 a!=b
// i=1,j=3,dp[1][3] = dp[1][1]=true
dp[i][j] = dp[i][j - 2];
// 表示匹配1次或者多次
// 匹配一次 例如s=ab,p=a*b,初始化dp[0][2]=true
// i=1,j=1时，dp[1][1]=dp[0][0]=true
// 当i=1,j=2时s.charAt(0) == p.charAt(0),让*匹配一次，dp[1][2]=dp[0][2]=true
// 匹配多次，例如s=aaab,p=a*b,前面略过，dp[3][2]=dp[2][2]=dp[1][2]=dp[0][2]=true
if (s.charAt(i - 1) == p.charAt(j - 2) || p.charAt(j - 2) == '.') {
// 这里需要合并两种情况的结果，就是0次或者多次，不能只写dp[i][j]=dp[i - 1][j]
// 这样会让*必须匹配一个或者多个导致错误
// 例如s=a,p=aa* ,0次的话dp[1][3]=dp[1][1]=true 但是dp[0][3]=false 所以需要合并0次的值
dp[i][j] = dp[i][j] || dp[i - 1][j];
}
}
}
}
// 返回结果，表示s和p是否匹配
return dp[m][n];
}
}C++版：
class Solution {
public:
bool isMatch(string s, string p)
{
int m = s.size();
int n = p.size();
// 定义一个bool类型的二维数组， dp[i][j]表示s的前i个字符与p的前j个字符是否匹配
// 这里m+1和n+1是为了处理空字符串或空数组的情况dp[0][0]表示两个空字符串是否匹配
vector<vector<bool>> dp(m + 1, vector<bool>(n + 1, false));
// 两个空字符串肯定匹配
dp[0][0] = true;
// 当s为空时，我们仍然需要知道与模式串是否匹配
// 比如a*是可以与空字符串匹配的，*可以代表前面字符出现0次或者多次
// 所以判断模式字符串中的*就行
// 后面的循环也需要用到这个初始化的值，否则都默认为false的话会导致错误
for (int j = 1; j <= n; j++)
{
if (p[j - 1] == '*')
{
// 当模式串的值为*时，说明前面的符号是可以为0的，所以值等于-2的值
dp[0][j] = dp[0][j - 2];
}
}
// 通过嵌套循环来将dp数组填满
// 外层循环遍历字符串中的每一个字符
for (int i = 1; i <= m; i++)
{
// 内层循环遍历模式串的每一个字符，对于字符串的每一个字符
// 检查它与模式p的前j个字符是否匹配。
for (int j = 1; j <= n; j++)
{
// 如果满足这个条件，说明当前的字符是匹配的，所以dp[i][j]取决于dp[i-1][j-1]
// 例如s=ab，p=ab，i=1,j=1,a=a,dp[1][1]=dp[0][0]=true
// 然后i=2,j=2，b=b,dp[2][2]=dp[1][1]=true
// 例如s=abc，p=a.c，i=1,j=1,a=a,dp[1][1]=dp[0][0]=true
// 然后i=2,j=2，s.charAt(1)=b，p.charAt(1)=. 这也是匹配的，所以dp[2][2]=dp[1][1]=true
// 然后i=3,j=3，c=c，dp[3][3] = dp[2][2] = true
if (s[i - 1] == p[j - 1] || p[j - 1] == '.')
{
dp[i][j] = dp[i - 1][j - 1];
}
// 如果模式串中当前字符为*，表示前面的字符可以匹配0次或多次。
else if (p[j - 1] == '*')
{
// 表示*匹配0次的时候，我们直接忽略*及其前面的字符
// 例如s="a"，p="ab*",s="",p="" dp[0][0]=true
// i=1,j=1,a=a,dp[1][1]=dp[0][0]=true,i=1,j=2 a!=b
// i=1,j=3,dp[1][3] = dp[1][1]=true
dp[i][j] = dp[i][j - 2];
// 表示匹配1次或者多次
// 匹配一次 例如s=ab,p=a*b,初始化dp[0][2]=true
// i=1,j=1时，dp[1][1]=dp[0][0]=true
// 当i=1,j=2时s.charAt(0) == p.charAt(0),让*匹配一次，dp[1][2]=dp[0][2]=true
// 匹配多次，例如s=aaab,p=a*b,前面略过，dp[3][2]=dp[2][2]=dp[1][2]=dp[0][2]=true
if (s[i - 1] == p[j - 2] || p[j - 2] == '.')
{
// 这里需要合并两种情况的结果，就是0次或者多次，不能只写dp[i][j]=dp[i - 1][j]
// 这样会让*必须匹配一个或者多个导致错误
// 例如s=a,p=aa* ,0次的话dp[1][3]=dp[1][1]=true 但是dp[0][3]=false 所以需要合并0次的值
dp[i][j] = dp[i][j] || dp[i - 1][j];
}
}
}
}
return dp[m][n];
}
};C版：
bool isMatch(const char* s, const char* p) {
// 获取s和p的长度
int m = strlen(s);
int n = strlen(p);
// 为dp动态规划数组分配内存。dp[i][j]代表s的前i个字符和p的前j个字符是否匹配
bool** dp = (bool**)malloc((m + 1) * sizeof(bool*));
for (int i = 0; i <= m; i++) {
dp[i] = (bool*)malloc((n + 1) * sizeof(bool));
// 初始化dp数组的每个值为false
memset(dp[i], false, (n + 1) * sizeof(bool));
}
// 两个空字符串必定匹配
dp[0][0] = true;
// 初始化模式串p的前j个字符和空字符串s的匹配情况
for (int j = 1; j <= n; j++) {
if (p[j - 1] == '*') {
// 如果p的当前字符是'*'，则看p中前j-2的字符和s是否匹配。
dp[0][j] = dp[0][j - 2];
}
}
// 遍历s和p，填充dp数组
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
// 如果s的当前字符和p的当前字符匹配，或p的当前字符是'.'
if (s[i - 1] == p[j - 1] || p[j - 1] == '.') {
// 取决于去掉当前字符后，两字符串的匹配情况
dp[i][j] = dp[i - 1][j - 1];
}
else if (p[j - 1] == '*') {
// 如果p的当前字符是'*'，则有两种情况
// 第一种：'*'匹配0次前面的字符
dp[i][j] = dp[i][j - 2];
// 第二种：'*'匹配1次或多次前面的字符
if (s[i - 1] == p[j - 2] || p[j - 2] == '.') {
// 注意这里是逻辑"或"操作，要么'*'匹配0次，要么匹配多次
dp[i][j] = dp[i][j] || dp[i - 1][j];
}
}
}
}
// 保存结果，并释放动态分配的内存
bool result = dp[m][n];
for (int i = 0; i <= m; i++) {
free(dp[i]);
}
free(dp);
return result;
}