In the Leetcode Regular Expression Matching problem solution in C++ programming Given an input string s and a pattern p, implement regular expression matching with support for ‘.’ and ‘*’ where:
‘.’ Matches any single character.
‘*’ Matches zero or more of the preceding element.
The matching should cover the entire input string (not partial).
Leetcode Regular Expression Matching problem solution in C++ programming
class Solution {
public:
bool match(string&s,string&p,vector<int>&mark,int i,int j){
while(i<(int)s.size()&&j<(int)p.size()){
if(s[i]==p[j]||'.'==p[j]){
if(mark[j]){//
if(match(s,p,mark,i,j+1))//
return true;
}else j++;
i++;
}else if(s[i]!=p[j]){
if(mark[j])j++;
else return false;
}
}
while(j<(int)p.size()&&mark[j])j++;
return i==(int)s.size()&&j==(int)p.size();
}
bool isMatch(string s, string p) {
vector<int>mark;//，mark[]=1,0
for(int i=0;i<(int)p.size();i++){//
if('*'==p[i]){
p.erase(p.begin()+i);
mark.back()=1;
i--;
}else mark.push_back(0);
}
for(int i=0;i<(int)p.size()-1;i++){//
if(p[i]==p[i+1]&&mark[i]&&mark[i+1]){
p.erase(p.begin()+i);
mark.erase(mark.begin()+i);
mark[i]=1;
i--;
}
}
int i=0,j=0;
return match(s,p,mark,i,j);
}
};Also read,
- Leetcode Regular Expression Matching problem solution in C
- Leetcode Regular Expression Matching problem solution in Java
- Leetcode Regular Expression Matching problem solution in Python
- Leetcode Regular Expression Matching problem solution in C#