Wildcard Matching

Problem Statement

Given an input string (s) and a pattern (p), implement wildcard pattern matching with support for '?' and '*' where:

• '?' Matches any single character.

• '*' Matches any sequence of characters (including the empty sequence).

The matching should cover the entire input string (not partial).

Example 1:

Input: s = "aa", p = "a"
Output: false
Explanation: "a" does not match the entire string "aa".

Example 2:

Input: s = "aa", p = "*"
Output: true
Explanation: '*' matches any sequence.

Example 3:

Input: s = "cb", p = "?a"
Output: false
Explanation: '?' matches 'c', but the second letter is 'a', which does not match 'b'.

Constraints:

• 0 <= s.length, p.length <= 2000

• s contains only lowercase English letters.

• p contains only lowercase English letters, '?' or '*'.

Intuition

For matching a character and ? 
We can match directly, reduce both by 1

But for * we match multiple using for loop 

Links

https://leetcode.com/problems/wildcard-matching/description/

Video Links

https://www.youtube.com/watch?v=ZmlQ3vgAOMo&ab_channel=takeUforward

Approach 1:

Memoization

C++

class Solution {
public:
    bool find_ans(string &s, string &t, int i, int j, vector<vector<int>> &dp){
        //Entire string matched
        if(i<0 and j<0)
            return true;

        if(i<0 and j>=0){
            /* 
            This entire block is added to take care of this type of testcase
            when first string gets exhausted and second has leading *

            abba
            *****abba

            To match all the leading * with empty 
            */
            int flag = 1;

            for(int start=j; start>=0; start--)
                if(t[start] != '*')
                    flag=0;

            if(flag)
                return true;

            return false;
        }

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

        if(dp[i][j] != -1)
            return dp[i][j];
            
        // Match single string
        if(s[i] == t[j] or t[j] == '?'){
            if( find_ans(s, t, i-1, j-1, dp) )
                return dp[i][j] = true;
        }
        // Match ith to 0 index for a single *
        else if(t[j] == '*'){
            for(int start=0; start<=i+1; start++) {
                if( find_ans(s, t, i-start, j-1, dp) )
                    return dp[i][j] = true;
            }
        }

        return dp[i][j] = false;
    }

    bool isMatch(string s, string t) {
        int m = s.size();
        int n = t.size();
        vector<vector<int>> dp (m, vector<int> (n,-1));

        return find_ans(s, t, m-1, n-1, dp);
    }
};
```

Approach 2:

C++

Approach 3:

C++

Similar Problems