题目
给你一个字符串 s 和一个字符规律 p,请你来实现一个支持 ‘.’ 和 ‘*’ 的正则表达式匹配。
‘.’ 匹配任意单个字符
‘*’ 匹配零个或多个前面的那一个元素
所谓匹配,是要涵盖 整个 字符串 s的,而不是部分字符串。
示例 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 = “cab”
输出:true
解释:因为 ‘*’ 表示零个或多个,这里 ‘c’ 为 0 个, ‘a’ 被重复一次。因此可以匹配字符串 “aab”。
示例 5:
输入:s = “mississippi” p = “misisp*.”
输出:false
- 方法一:动态规划
class Solution {
public:
bool isMatch(string s, string p) {
vector<vector<bool> > dp(s.size()+1,vector<bool>(p.size()+1));
//p和s均为空串时匹配成功
dp[0][0] = true;
//i从0开始,表示s为空串时也要与p进行匹配
//j从1开始,表示p为空串时不需要匹配,因为只有此时s也为空串才匹配成功
//dp[i][j]表示s前i个字符与p的前j个字符是否匹配
for(int i=0; i<=s.size(); i++){
for(int j=1; j<=p.size(); j++){
//如果p的第j个字符为*
if(p[j-1] == '*'){
//如果s的第i个字符与p的第j-2个字符成功匹配,此时可认为*前的字符出现了0次,匹配是否成功看子问题dp[i][j-2]
dp[i][j] = dp[i][j-2];
//如果不符合前一种情况
if(!dp[i][j]){
//如果s的第i个字符和p的j-1个字符匹配成功,此时可认为*前的字符出现了0次,匹配是否成功看子问题dp[i-1][j]
if(i==0){
continue;//防止i下标越界,且该情况不会存在于s是空串
}else if(s[i-1] == p[j-2] || p[j-2] == '.'){
dp[i][j] = dp[i-1][j];
}
}
}else{//p的第j个字符不是*,只需比较当前字符
if(i==0){
//i=0表示s为空串,此时想成功匹配只能是p为空串或p为x*的重复
continue;
}else if(s[i-1]==p[j-1]||p[j-1] == '.'){
dp[i][j] = dp[i-1][j-1];
}
}
}
}
return dp[s.size()][p.size()];
}
};
class Solution {
public:
bool isMatch(string s, string p) {
vector<vector<bool>> dp(s.size()+1, vector<bool>(p.size()+1));
dp[0][0] = true;
//处理当s为空时p的匹配情况
for(int i=2; i<=p.size(); i+=2){
if(p[i-1] == '*'){
dp[0][i] = true;
}else{
break;
}
}
//处理s和p均非空时的匹配情况
for(int i=1; i<=s.size(); i++){
for(int j=1; j<=p.size(); j++){
//如果p当前的字符为*,有两种情况
//一种时x*一次都没有出现,此时看dp[i][j-2]是否匹配
//一种是x*出现了至少一次,此时看dp[i-1][j-2]是否匹配,dp[i-1][j]是对该情况的优化,相当于x*已经出现过一次了
if(p[j-1]=='*'){
dp[i][j] = dp[i][j-2];
if(!dp[i][j] && (p[j-2]==s[i-1]||p[j-2]=='.')){
dp[i][j] = dp[i-1][j];
}
}else{//如果不是*则比较当前字符是否匹配
if(p[j-1]=='.' || p[j-1]==s[i-1]){
dp[i][j] = dp[i-1][j-1];
}
}
}
}
return dp[s.size()][p.size()];
}
};
- 时间复杂度O(mn)
- 空间复杂度O(mn)
- 思路
- dp[i][j]表示s的前i个字符和p的前j个字符是否匹配,匹配则为true。对于动态规划问题,一般空出0号位处理越界等情况,该题中0号表示空串。
- 确定递推公式
- 如果模式串第j个字符为*
- 如果dp[i][j-2]==true,那么dp[i][j]为true,可以把该位置的*与它之前的元素看成空串
- 如果dp[i-1][j-2]为true的话,只要s[i]和p[j-1]匹配,dp[i][j]也为true.dp[i-1][j-2]与dp[i-1][j]相差只有一个前置字符和*,故可优化为dp[i-1][j]。
- 如果模式串第j个不为*,则为常规匹配,如果当前位置不匹配则为false,匹配则为dp[i-1][j-1]
- i-1存在,为避免下标越界,i不能为0
- 如果模式串第j个字符为*
- 初始化:dp[0][0]为true表示两个空串可以匹配
- 确定遍历顺序
- 方法二:递归
class Solution {
public:
bool isMatch(string s, string p) {
return Match(s.c_str(),p.c_str());
}
bool Match(const char* s, const char *p){
if(*p == '\0') return *s == '\0';
if(*(p+1) != '*'){
if(*p == *s || (*p == '.'&& *s!='\0')){
return Match(s+1,p+1);
}else{
return false;
}
}else{
while(*p == *s || (*p == '.'&& *s!='\0')){
if(Match(s,p+2))
return true;
s++;
}
return Match(s,p+2);
}
}
};
- 思路
- 如果p为空,s为空则匹配,否则不匹配
- 根据*(p+1)分为两种情况
- 如果不是*,则匹配当前的s和p,如果二者的字符相等,递归调用匹配下一个字符,否则返回false
- 如果是*,匹配当前的p和s
- 如果不能匹配,递归调用匹配s和p+2
- 如果能匹配,递归调用匹配下一个p,如果匹配成功则返回true,否则s++,知道p与s不匹配,递归调用匹配s和p+2。
动态规划参考详解