Coding_Programs/Wildcard Matching.cpp at Main · Pratik19ap/Coding_Programs · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
//Programmed in C++ | Author: Anshuman Pratik
//For * take 2 cases, one when it is Empty string followed by reducing pattern pointer by 1, and other when replaced by *char i.e. for b in String, we can replace with *b so that pointer in pattern remains at * after cancelling out from String
class Solution {
public:
    bool solve(string& str, string& pattern, int i, int j, vector<vector<int> >& dp) {
        //base case
        if(i<0 && j<0)
            return true;

        if(i>=0 && j<0)
            return false;

        if(i<0 && j>=0) {
            for(int k=0; k<=j; k++) {
                if(pattern[k] != '*') {
                    return false;
                }
            }
            return true;
        }

        if(dp[i][j] != -1)
            return dp[i][j];

        //Matching of String and Pattern
        if(str[i] == pattern[j] || pattern[j] == '?')
            return dp[i][j] = solve(str, pattern, i-1, j-1, dp);
        else if(pattern[j] == '*')
            return dp[i][j] = ( solve(str, pattern, i-1, j, dp) || solve(str, pattern, i, j-1, dp) );
        else
            return false;

    }
    bool isMatch(string s, string p) {
        vector<vector<int> > dp(s.length(), vector<int>(p.length(), -1));
        return solve(s, p, s.length()-1, p.length()-1, dp);
    }
};