Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- class Solution {
- public:
- bool isMatch(string s, string p) {
- memset(dp,-1,sizeof(dp));
- return solve(0,0,s,p);
- }
- private:
- int dp[21][21];
- bool solve(int i,int j,string& s,string& p){
- if(j==p.length()){
- return i==s.length();
- }
- bool asteriskAhead = (j+1<p.length()) && (p[j+1]=='*');
- if(i==s.length()){
- return asteriskAhead && solve(i,j+2,s,p);
- }
- if(dp[i][j] != -1) return dp[i][j];
- bool firstMatch = (i<s.length()) && (s[i]==p[j]) || (p[j] == '.');
- if(asteriskAhead){
- bool zeroMatch = solve(i,j+2,s,p);
- bool oneOrMoreMatch = firstMatch && solve(i+1,j,s,p);
- return dp[i][j] = zeroMatch || oneOrMoreMatch;
- }
- else{
- return dp[i][j] = firstMatch && solve(i+1,j+1,s,p);
- }
- }
- };
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
